import java.io.*; import java.util.*; public class Main { static List> links; static class Node implements Comparable { int to; int cost; Node(int to, int cost) { this.to = to; this.cost = cost; } public int compareTo(Node o) { return this.cost - o.cost; } } //from에서 to로 가는 최단경로 static int djk(int n, int from, int to) { int[] dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[from] = 0; PriorityQueue pq = new PriorityQueue<>(); for (int[] nxt : links.get(from)) { //시작점과 연결된 곳 pq.add(new Node(nxt[0], nxt[1])); dist[nxt[0]] = nxt[1]; } while (!pq.isEmpty()) { Node now = pq.poll(); int idx = now.to; int cost = now.cost; if (idx == to) { //목적지 도달 break; } for (int[] nxt : links.get(idx)) { int nxtIdx = nxt[0]; int nxtCost = nxt[1] + cost; if (dist[nxtIdx] == Integer.MAX_VALUE) { pq.add(new Node(nxtIdx, nxtCost)); dist[nxtIdx] = nxtCost; } } } return dist[to]; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); // int t = Integer.parseInt(br.readLine()); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); //정점개수 int e = Integer.parseInt(st.nextToken()); //간선개수 links = new ArrayList<>(); //i에서 [j, c] for (int i = 0; i < n; i++) { links.add(new ArrayList<>()); } for (int i = 0; i < e; i++) { st = new StringTokenizer(br.readLine()); // a<->b int a = Integer.parseInt(st.nextToken()) - 1; int b = Integer.parseInt(st.nextToken()) - 1; int c = Integer.parseInt(st.nextToken()); //가중치 links.get(a).add(new int[]{b, c}); links.get(b).add(new int[]{a, c}); } st = new StringTokenizer(br.readLine()); //반드시 거쳐야 하는 정점 int v1 = Integer.parseInt(st.nextToken()) - 1; int v2 = Integer.parseInt(st.nextToken()) - 1; // 0 -> n-1까지 가는 최단경로 // 0 -> v1 -> v2 -> n-1 // 0 -> v2 -> v1 -> n-1 // 둘 중 하나 int zeroToV1 = djk(n, 0, v1); int zeroToV2 = djk(n, 0, v2); int v1ToV2 = djk(n, v1, v2); // == v2ToV1 int v1ToEnd = djk(n, v1, n-1); int v2ToEnd = djk(n, v2, n-1); //경로 없음 if ((zeroToV1 == Integer.MAX_VALUE || zeroToV2 == Integer.MAX_VALUE) && (v1ToV2 == Integer.MAX_VALUE) && (v1ToEnd == Integer.MAX_VALUE || v2ToEnd == Integer.MAX_VALUE)) { System.out.println(-1); } else { System.out.println(Math.min(zeroToV1 + v1ToV2 + v2ToEnd, zeroToV2 + v1ToV2 + v1ToEnd)); } } }

제출 #123772

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: