import java.io.*; import java.util.Arrays; import java.util.PriorityQueue; public class Main { static int[][] graph; static int n; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] str = br.readLine().split(" "); n = Integer.parseInt(str[0]); int e = Integer.parseInt(str[1]); // 그래프 정보 입력 graph = new int[n + 1][n + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) graph[i][j] = 0; else graph[i][j] = -1; } } for (int i = 0; i < e; i++) { str = br.readLine().split(" "); int a = Integer.parseInt(str[0]); int b = Integer.parseInt(str[1]); int c = Integer.parseInt(str[2]); // 양방향 그래프 graph[a][b] = c; graph[b][a] = c; } // 각 노드에서 다른 노드까지의 최단거리 구하기 for (int u = 1; u < n; u++) { for (int v = u; v <= n; v++) { if (u == v) continue; findMinRoute(u, v); } } /*for(int i =1; i<=n; i++) { System.out.println(Arrays.toString(graph[i])); }*/ str = br.readLine().split(" "); int v1 = Integer.parseInt(str[0]); int v2 = Integer.parseInt(str[1]); checkResult(v1, v2); } static void findMinRoute(int u, int v) { for (int i = 1; i <= n; i++) { if (graph[u][v] == -1) { if (graph[u][i] != -1 && graph[i][v] != -1) { graph[u][v] = graph[u][i] + graph[i][v]; graph[v][u] = graph[u][i] + graph[i][v]; } } else { if (graph[u][i] != -1 && graph[i][v] != -1) { int min = Math.min(graph[u][v], graph[u][i] + graph[i][v]); graph[u][v] = min; } } } } static void checkResult(int v1, int v2) { int case1 = -1; int case2 = -1; int answer; if (graph[v1][v2] == -1) { answer = -1; } else { if (graph[1][v1] != -1 && graph[v2][n] != -1) { case1 = graph[1][v1] + graph[v2][n]; //System.out.println("entered case1 => " + case1); } if (graph[1][v2] != -1 && graph[v1][n] != -1) { case2 = graph[1][v2] + graph[v1][n]; //System.out.println("entered case2 => " + case2); } if (case1 >= 0 && case2 >= 0) { answer = Math.min(case1, case2) + graph[v1][v2]; } else if (case1 < 0 && case2 < 0) { answer = -1; } else if (case1 < 0) { answer = case2 + graph[v1][v2]; } else { answer = case1 + graph[v1][v2]; } } System.out.println(answer); } }

제출 #15579

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: