import java.util.*; import java.io.*; public class Main { static int N, E; static List> graph; static int[] dist; static final int INF = Integer.MAX_VALUE; public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(reader.readLine()); N = Integer.parseInt(st.nextToken()); E = Integer.parseInt(st.nextToken()); dist = new int[N + 1]; Arrays.fill(dist, INF); graph = new ArrayList<>(); for (int i = 0; i <= N; i++) graph.add(new ArrayList<>()); for (int i = 0; i < E; i++) { st = new StringTokenizer(reader.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); graph.get(u).add(new Node(v, w)); graph.get(v).add(new Node(u, w)); } st = new StringTokenizer(reader.readLine()); int v1 = Integer.parseInt(st.nextToken()); int v2 = Integer.parseInt(st.nextToken()); long sum1 = 0, sum2 = 0; dijkstra(1); sum1 += dist[v1]; Arrays.fill(dist, INF); dijkstra(v1); sum1 += dist[v2]; Arrays.fill(dist, INF); dijkstra(v2); sum1 += dist[N]; Arrays.fill(dist, INF); dijkstra(1); sum2 += dist[v2]; Arrays.fill(dist, INF); dijkstra(v2); sum2 += dist[v1]; Arrays.fill(dist, INF); dijkstra(v1); sum2 += dist[N]; Arrays.fill(dist, INF); if (sum1 >= INF && sum2 >= INF) System.out.println(-1); else System.out.println(Math.min(sum1, sum2)); } static void dijkstra(int start) { PriorityQueue q = new PriorityQueue<>((n1, n2) -> n1.cost - n2.cost); q.offer(new Node(start, 0)); dist[start] = 0; while (!q.isEmpty()) { Node now = q.poll(); if (dist[now.nextNode] < now.cost) continue; for (Node next: graph.get(now.nextNode)) { int newCost = next.cost + dist[now.nextNode]; if (newCost < dist[next.nextNode]) { dist[next.nextNode] = newCost; q.offer(new Node(next.nextNode, newCost)); } } } } static class Node { int nextNode; int cost; public Node(int nextNode, int cost) { this.cost = cost; this.nextNode = nextNode; } } }

코드 #6522