package BJ_0x1D_check; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; import java.util.StringTokenizer; public class BJ_1504 { static List> list; static boolean[] check; static int[] dist; static int N; static class Node implements Comparable { int idx; int w; public Node(int idx, int w) { this.idx = idx; this.w = w; } @Override public int compareTo(Node o) { return w - o.w; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); int E = Integer.parseInt(st.nextToken()); list = new ArrayList<>(); for(int i = 0; i <= N; i++){ list.add(new ArrayList<>()); } for(int i = 0; i < E; i++){ st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); list.get(u).add(new Node(v, w)); } st = new StringTokenizer(br.readLine()); int v1 = Integer.parseInt(st.nextToken()); int v2 = Integer.parseInt(st.nextToken()); int first = 0; //1 -> v1 -> v2 -> N first += dijkstra(1, v1); first += dijkstra(v1, v2); first += dijkstra(v2, N); //1 -> v2 -> v1 -> N int second = 0; second += dijkstra(1, v2); second += dijkstra(v2, v1); second += dijkstra(v1, N); int min = (first >= 200000000 && second >= 200000000) ? -1 : Math.min(first, second); System.out.println(min); } static int dijkstra(int start, int end){ check = new boolean[N + 1]; dist = new int[N + 1]; for(int i = 0; i <= N; i++){ dist[i] = 200000000; } PriorityQueue queue = new PriorityQueue<>(); queue.add(new Node(start, 0)); dist[start] = 0; while(!queue.isEmpty()){ Node poll = queue.poll(); if(check[poll.idx]) continue; check[poll.idx] = true; for (Node node : list.get(poll.idx)) { if(!check[node.idx] && dist[node.idx] > dist[poll.idx] + node.w){ queue.add(node); dist[node.idx] = dist[poll.idx] + node.w; } } } return dist[end]; } }

제출 #10795

제출 정보

제출 결과

제출 코드

찾은 반례