on
[BOJ] 백준 [5719] 거의 최단 경로 JAVA
[BOJ] 백준 [5719] 거의 최단 경로 JAVA
import java.util. * ;
import java.io. * ;
import java.util.stream.Collectors;
public class Main{
static int N,E;
static ArrayList < Node > [] list;
static int [] distance;
static ArrayList < Integer > [] pathList;
public static void main( String [] args) throws IOException {
BufferedReader br = new BufferedReader( new InputStreamReader( System . in ));
String input;
while ( ! (input = br.readLine()). equals ( "0 0" )){
int [] e = Arrays.stream(input. split ( " " )).mapToInt(Integer:: parseInt ).toArray();
int [] point = Arrays.stream(br.readLine(). split ( " " )).mapToInt(Integer:: parseInt ).toArray();
N = e[ 0 ]; E = e[ 1 ]; // 노드 , 엣지 개수 초기화
list = new ArrayList[N];
pathList = new ArrayList[N]; // 경로 역추적을 하기위한 배열
distance = new int [N];
for ( int i = 0 ;i < N;i + + ) {
list[i] = new ArrayList < > ();
pathList[i] = new ArrayList < > ();
}
for ( int i = 0 ;i < E;i + + ){
e = Arrays.stream(br.readLine(). split ( " " )).mapToInt(Integer:: parseInt ).toArray();
list[e[ 0 ]]. add ( new Node(e[ 1 ],e[ 2 ]));
}
int len = findShortestPath(point[ 0 ], point[ 1 ]);
removePath(point[ 1 ]);
int ret = findShortestPath(point[ 0 ], point[ 1 ]);
if (ret = = Integer.MAX_VALUE | | len = = Integer.MAX_VALUE)
System . out . println ( - 1 );
else
System . out . println (ret);
}
}
static int findShortestPath( int start, int end){
;
Arrays.fill(distance,Integer.MAX_VALUE);
PriorityQueue < Node > q = new PriorityQueue < > ();
q. add ( new Node(start, 0 ));
distance[start] = 0 ;
while ( ! q.isEmpty()){
Node cur = q.poll();
if (distance[cur.node] < cur.weight) continue ;
for (Node next : list[cur.node]) {
if (distance[next.node] > distance[cur.node] + next.weight) {
distance[next.node] = distance[cur.node] + next.weight;
q. add ( new Node(next.node,distance[next.node]));
pathList[next.node].clear();
pathList[next.node]. add (cur.node);
} else if (distance[next.node] = = distance[cur.node] + next.weight) {
pathList[next.node]. add (cur.node);
}
}
}
return distance[end];
}
static void removePath( int end){
LinkedList < Integer > queue = new LinkedList < > ();
queue. add (end);
while ( ! queue.isEmpty()){
int poll = queue.poll();
pathList[poll].forEach(e - > list[e].stream().filter(x - > x.node = = poll).findAny().ifPresent(x - > {
list[e].remove(x);
queue. add (e);
}));
}
}
static class Node implements Comparable < Node > {
int node;
int weight;
public Node( int node, int weight) {
this .node = node;
this .weight = weight;
}
@Override
public int compareTo(Node o) {
return this .weight - o.weight;
}
}
}
from http://katastrophe.tistory.com/45 by ccl(A) rewrite - 2021-10-02 20:00:21