import java.util.*; /* Input: 4 6 1 2 3 2 3 3 3 4 1 1 3 5 2 4 5 1 4 4 2 3 Output: 7 */ public class Main { static int N; static List> graph; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); int E = sc.nextInt(); long result = Integer.MAX_VALUE; graph = new ArrayList<>(); for (int i = 0; i < N + 1; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < E; i++) { int startNode = sc.nextInt(); int endNode = sc.nextInt(); int cost = sc.nextInt(); graph.get(startNode).add(new Node(endNode, cost)); graph.get(endNode).add(new Node(startNode, cost)); } int v1 = sc.nextInt(); int v2 = sc.nextInt(); result = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N); result = Math.min(result, dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N)); if (result <= 0) result = -1; if (result >= Integer.MAX_VALUE) result = -1; System.out.println(result); } public static int dijkstra(int startNode, int endNode) { PriorityQueue q = new PriorityQueue<>(Comparator.comparingInt(o -> o.cost)); q.add(new Node(startNode, 0)); int[] distance = new int[N + 1]; for (int i = 0; i < N + 1; i++) { distance[i] = Integer.MAX_VALUE; } distance[startNode] = 0; while (!q.isEmpty()) { Node node = q.poll(); if (distance[node.index] < node.cost) continue; List adjacentNodes = graph.get(node.index); for (Node adjacentNode : adjacentNodes) { if (distance[node.index] + adjacentNode.cost < distance[adjacentNode.index]) { distance[adjacentNode.index] = distance[node.index] + adjacentNode.cost; q.add(new Node(adjacentNode.index, distance[adjacentNode.index])); } } } return distance[endNode] == Integer.MAX_VALUE ? Integer.MIN_VALUE : distance[endNode]; } static class Node { int index, cost; public Node(int index, int cost) { this.index = index; this.cost = cost; } } }

제출 #12356

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: