import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int M = Integer.parseInt(br.readLine()); List> map = new ArrayList<>(); for (int i = 0; i < N + 1; i++) { map.add(new ArrayList()); } for (int i = 0; i < M; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); int idx = Integer.parseInt(st.nextToken()); // 앞에께 가는 곳, 뒤에께 비용 map.get(idx).add(Integer.parseInt(st.nextToken()) * 100000 + Integer.parseInt(st.nextToken())); } StringTokenizer st3 = new StringTokenizer(br.readLine()); int start = Integer.parseInt(st3.nextToken()); int end = Integer.parseInt(st3.nextToken()); int[] visitCost = new int[N + 1]; boolean[] visited = new boolean[N + 1]; ArrayDeque q = new ArrayDeque<>(); q.add(new Where(start, end, 0)); bfs(map, visitCost, visited, q); System.out.println(visitCost[end]); } static void bfs(List> map, int[] visitCost, boolean[] visited, ArrayDeque q) { while (!q.isEmpty()) { Where here = q.pop(); int now = here.now; int end = here.end; int cost = here.cost; if (visited[end]&&cost > visitCost[end]) return; if(now == end && (visitCost[now] > cost || !visited[now])) { visitCost[end] = cost; visited[end] = true; } if(now != end && (visitCost[now] > cost || !visited[now])) { visitCost[now] = cost; visited[now] = true; for (int i = 0; i < map.get(now).size(); i++) { q.add(new Where(map.get(now).get(i) / 100000, end, cost + map.get(now).get(i) % 100000)); } } } } static class Where{ int now; int end; int cost; public Where(int now, int end, int cost) { this.now = now; this.end = end; this.cost = cost; } } }

제출 #37941

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: