import java.io.*; import java.util.*; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringBuilder sb = new StringBuilder(); static StringTokenizer st = null; static class Node implements Comparable { int v, w; Node() {} Node(int v, int w) { this.v = v; this.w = w; } @Override public int compareTo(Node other) { return this.w - other.w; } } static final int MAX_N = 800; static final int INF = 1_000 * MAX_N; static int N, E; static int V1, V2; static List[] adj = new List[MAX_N + 1]; static int[] minDist = new int[MAX_N + 1]; static int dijkstra(int from, int to) { if(from == to) return 0; Arrays.fill(minDist, INF); PriorityQueue q = new PriorityQueue<>(); q.offer(new Node(from, 0)); minDist[from] = 0; while(!q.isEmpty()) { Node node = q.poll(); int u = node.v, w = node.w; for(Node nextNode : adj[u]) { int v = nextNode.v; int dist = nextNode.w + w; if(dist < minDist[v]) { minDist[v] = dist; q.offer(new Node(v, dist)); if(v == to) return dist; } } } return -1; } static int getLength(int[] path) { int pathLength = 0; for(int i = 1; i < path.length; ++i) { int len = dijkstra(path[i - 1], path[i]); if(len < 0) return -1; pathLength += len; } return pathLength; } static int solution() { int pathLength = 0; // 1 -> v1 -> v2 -> N int[] pathA = new int[] {1, V1, V2, N}; pathLength = getLength(pathA); if(pathLength >= 0) return pathLength; // 1 -> v2 -> v1 -> N int[] pathB = new int[] {1, V2, V1, N}; pathLength = getLength(pathB); if(pathLength >= 0) return pathLength; return pathLength; } public static void main(String[] args) throws IOException { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); E = Integer.parseInt(st.nextToken()); for(int i = 1; i <= N; ++i) adj[i] = 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()); adj[u].add(new Node(v, w)); } st = new StringTokenizer(br.readLine()); V1 = Integer.parseInt(st.nextToken()); V2 = Integer.parseInt(st.nextToken()); System.out.println(solution()); } }

제출 #23737

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: