import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int N, M; static ArrayList> graph; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; N = Integer.parseInt(br.readLine()); M = Integer.parseInt(br.readLine()); graph = new ArrayList>(); for(int i = 0; i <= N; i++) { graph.add(new ArrayList<>()); } for(int i = 1; i <= M; i++) { st = new StringTokenizer(br.readLine()); int start = Integer.parseInt(st.nextToken()); int end = Integer.parseInt(st.nextToken()); int cost = Integer.parseInt(st.nextToken()); graph.get(start).add(new Node(end, cost)); } st = new StringTokenizer(br.readLine()); int start = Integer.parseInt(st.nextToken()); int end = Integer.parseInt(st.nextToken()); System.out.println(dijkstra(start, end)); } static int dijkstra(int start, int end) { boolean visited[] = new boolean[N + 1]; int dist[] = new int[N + 1]; PriorityQueue pq = new PriorityQueue<>((a, b) -> b.cost - a.cost); pq.offer(new Node(start, 0)); for(int i = 0; i <= N; i++) { dist[i] = Integer.MAX_VALUE; } dist[start] = 0; while(!pq.isEmpty()) { Node curNode = pq.poll(); if(visited[curNode.dest]) continue; visited[curNode.dest] = true; for(Node next : graph.get(curNode.dest)) { if(dist[next.dest] > dist[curNode.dest] + next.cost) { dist[next.dest] = dist[curNode.dest] + next.cost; pq.offer(new Node(next.dest, dist[next.dest])); } } } return dist[end]; } } class Node { int dest; int cost; Node(int dest, int cost) { this.dest = dest; this.cost = cost; } }

제출 #63759

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: