import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashMap; import java.util.LinkedList; import java.util.Map; import java.util.Queue; import java.util.Set; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int V = Integer.parseInt(st.nextToken()); int E = Integer.parseInt(st.nextToken()); int[] dist = new int[V + 1]; Arrays.fill(dist, Integer.MAX_VALUE); Map plist = new HashMap<>(); int K = Integer.parseInt(br.readLine()); for (int i = 0; i < V; i++) { plist.put(i + 1, new Point()); } for (int i = 0; i < E; i++) { st = new StringTokenizer(br.readLine()); int v = Integer.parseInt(st.nextToken()); int u = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); plist.get(v).setAdj(u, w); } boolean[] visit = new boolean[V + 1]; Queue que = new LinkedList<>(); que.add(K); while(!que.isEmpty()) { int t = que.poll(); Set adjs = plist.get(t).getAdj().keySet(); for (Integer adj : adjs) { if(plist.get(t).getResult() + plist.get(t).getAdj().get(adj) < dist[adj]) { plist.get(adj).setResult(plist.get(t).getResult() + plist.get(t).getAdj().get(adj)); dist[adj] = plist.get(adj).getResult(); } if(!visit[adj]) { visit[adj] = true; que.add(adj); } } } dist[K] = 0; for (int i = 0; i < V; i++) { if(dist[i+1] == Integer.MAX_VALUE) { System.out.println("INF"); } else System.out.println(dist[i + 1]); } } } class Point { private int result; private Map adj; public Point() { adj = new HashMap<>(); } public void setAdj(int u, int w) { if(this.adj.get(u) != null) { this.adj.put(u, Math.min(w, this.adj.get(u))); } else this.adj.put(u, w); } public Map getAdj() { return this.adj; } public void setResult(int n) { this.result = n; } public int getResult() { return this.result; } }

제출 #53132

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: