import java.awt.Point; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { static final int INF = Integer.MAX_VALUE/2; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer stk; static ArrayList> nodes = new ArrayList<>(); static PriorityQueue pq = new PriorityQueue<>(); static int nodeCnt,edgeCnt,stNode; static int[] costs; static boolean[] visited; public static void main(String[] args) throws IOException { init(); dijk(); print(); } private static void print() { StringBuilder sb = new StringBuilder(); for (int i = 1; i <= nodeCnt; i++) { sb.append( (costs[i] != INF)?costs[i]:"INF").append("\n"); } System.out.println(sb.toString()); } private static void dijk() { int minNode = stNode; for (int i = 0; i < nodeCnt; i++) { int minCost = INF; minNode = pq.poll().nodeNum; for (int j = 0; j < nodeCnt; j++) { if (!visited[j] && minCost > costs[j] ) { minCost = costs[j]; minNode = j; } } visited[minNode] = true; ArrayList node = nodes.get(minNode); for ( Edge e: node) { int cost = e.cost; int to = e.to; costs[to] = Math.min (costs[to] , costs[minNode] + cost); } } } private static void init() throws IOException { stk = new StringTokenizer(br.readLine()); nodeCnt = Integer.parseInt(stk.nextToken()); edgeCnt = Integer.parseInt(stk.nextToken()); stNode = Integer.parseInt(br.readLine()); for (int i = 0; i <= nodeCnt; i++) nodes.add(new ArrayList<>()); costs = new int[nodeCnt+1]; visited = new boolean[nodeCnt+1]; Arrays.fill(costs, INF); costs[stNode] = 0; visited[stNode] = true; for (int i = 0; i < edgeCnt; i++) { stk = new StringTokenizer(br.readLine()); int from = Integer.parseInt(stk.nextToken()); int to = Integer.parseInt(stk.nextToken()); int cost = Integer.parseInt(stk.nextToken()); nodes.get(from).add(new Edge(to,cost)); } for (int i = 1; i<= nodeCnt; i++) pq.add(new Node(i)); } static class Edge{ int to; int cost; public Edge(int to, int cost) { super(); this.to = to; this.cost = cost; } } static class Node implements Comparable{ int nodeNum; @Override public int compareTo(Node o) { // TODO Auto-generated method stub return costs[this.nodeNum] - costs[o.nodeNum]; } public Node(int n) { this.nodeNum = n; } } }

제출 #45560

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: