import java.util.*; public class Main { static class Node { int to; long weight; public Node(int to, long weight) { this.to = to; this.weight = weight; } } public static void main(String[] args) { solution(); } static void solution() { Scanner sc = new Scanner(System.in); int start; int n = sc.nextInt(); int e = sc.nextInt(); List> graph = new ArrayList<>(); for (int i = 0; i <= n; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < e; i++) { int a = sc.nextInt(); int b = sc.nextInt(); int weight = sc.nextInt(); graph.get(a).add(new Node(b, weight)); graph.get(b).add(new Node(a, weight)); } int v1 = sc.nextInt(); int v2 = sc.nextInt(); PriorityQueue pq = new PriorityQueue<>(Comparator.comparingLong(elem -> elem.weight)); //1 -> v1 //v1 < v2? long[] dist = new long[n + 1]; Arrays.fill(dist, Integer.MAX_VALUE); dist[1] = 0; pq.add(new Node(1, 0)); while (!pq.isEmpty()) { Node current = pq.poll(); for (Node node : graph.get(current.to)) { long newDist = dist[current.to] + node.weight; if (dist[node.to] > newDist) { dist[node.to] = newDist; pq.add(new Node(node.to, newDist)); } } } //v1 -> v2 if (dist[v1] > dist[v2]) { start = v2; } else { start = v1; } for (int i = 0; i < dist.length; i++) { if (i == start) { continue; } dist[i] = Integer.MAX_VALUE; } pq.add(new Node(start, dist[start])); while (!pq.isEmpty()) { Node current = pq.poll(); for (Node node : graph.get(current.to)) { long newDist = dist[current.to] + node.weight; if (dist[node.to] > newDist) { dist[node.to] = newDist; pq.add(new Node(node.to, newDist)); } } } //v2 -> end if (start == v1) { start = v2; } else { start = v1; } for (int i = 0; i < dist.length; i++) { if (i == start) { continue; } dist[i] = Integer.MAX_VALUE; } pq.add(new Node(start, dist[start])); while (!pq.isEmpty()) { Node current = pq.poll(); for (Node node : graph.get(current.to)) { long newDist = dist[current.to] + node.weight; if (dist[node.to] > newDist) { dist[node.to] = newDist; pq.add(new Node(node.to, newDist)); } } } if (dist[n] == Integer.MAX_VALUE) { dist[n] = -1; } System.out.print(dist[n]); sc.close(); } }

제출 #11220

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: