import java.io.*; import java.nio.channels.InterruptedByTimeoutException; import java.util.*; public class Main { static class Edge implements Comparable { int now; int cost; public Edge(int now, int cost) { this.now = now; this.cost = cost; } @Override public int compareTo(Edge o) { return this.cost - o.cost; } } static int N; static List> graph; static boolean possible1 = true; static boolean possible2 = true; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()); graph = new ArrayList<>(); for (int i = 0; i < N; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < M; i++) { StringTokenizer st2 = new StringTokenizer(br.readLine()); int from = Integer.parseInt(st2.nextToken())-1; int to = Integer.parseInt(st2.nextToken())-1; int cost = Integer.parseInt(st2.nextToken()); graph.get(from).add(new Edge(to, cost)); graph.get(to).add(new Edge(from, cost)); } StringTokenizer st3 = new StringTokenizer(br.readLine()); int v1 = Integer.parseInt(st3.nextToken()) - 1; int v2 = Integer.parseInt(st3.nextToken()) - 1; // 0 -> v1 -> v2 -> N-1 int case1 = dijkstra(0, v1) + dijkstra(v1, v2) + dijkstra(v2, N - 1); // 0 -> v2 -> v2 -> N-1 int case2 = dijkstra(0, v2) + dijkstra(v2, v1) + dijkstra(v1, N - 1); if(case1>=1600000 && case2 >= 1600000) { System.out.println(-1); return; } System.out.println(Math.min(case1, case2)); } private static int dijkstra(int start, int end) { if(start==end) return 0; int[] costSave = new int[N]; Arrays.fill(costSave, Integer.MAX_VALUE); PriorityQueue pq = new PriorityQueue<>(); costSave[start] = 0; pq.add(new Edge(start, 0)); while (!pq.isEmpty()) { Edge where = pq.poll(); int here = where.now; for (Edge e : graph.get(here)) { int newCost = e.cost + costSave[here]; if (newCost < costSave[e.now]) { if (e.now == end) { return newCost; } pq.add(new Edge(e.now, newCost)); costSave[e.now] = newCost; } } } return 1600000; } }

제출 #43534

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: