import java.io.BufferedReader; import java.io.IOException; import java.io.StringReader; import java.util.ArrayList; import java.util.HashMap; import java.util.PriorityQueue; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int cityCnt = Integer.parseInt(br.readLine()); int busyCnt = Integer.parseInt(br.readLine()); HashMap> map = new HashMap<>(); for (int i = 0; i < cityCnt; i++) { map.put(i+1, new ArrayList<>()); } for (int i = 0; i < busyCnt; i++) { String[] data = br.readLine().split(" "); int start = Integer.parseInt(data[0]); int end = Integer.parseInt(data[1]); int cost = Integer.parseInt(data[2]); map.get(start).add(new Info(end, cost)); } int[] cost = new int[cityCnt+1]; boolean[] visited = new boolean[cityCnt+1]; for (int i = 1; i < cost.length; i++) { cost[i] = Integer.MAX_VALUE; } String[] init = br.readLine().split(" "); int initStart = Integer.parseInt(init[0]); int initDestination = Integer.parseInt(init[1]); PriorityQueue queue = new PriorityQueue<>((o1, o2) -> { return Integer.compare(o1.getCost(), o2.getCost()); }); queue.add(new Info(initStart, 0)); cost[initStart] = 0; while (!queue.isEmpty()) { Info current = queue.poll(); if (visited[current.getValue()]) continue; visited[current.getValue()] = true; for (Info next : map.get(current.getValue())) { if (cost[current.getValue()] + next.getCost() < cost[next.getValue()]) { queue.add(next); cost[next.getValue()] = cost[current.getValue()] + next.getCost(); } } } System.out.println(cost[initDestination]); } private static class Info { int value; int cost; public Info(int value, int cost) { this.value = value; this.cost = cost; } public int getValue() { return value; } public int getCost() { return cost; } } }

제출 #119816

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: