import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { timeMachine(); } public static class Edge { Map edges; public Edge() { edges = new HashMap<>(); } public void add(int dst, int cost) { edges.put(dst, cost); } } public static void timeMachine() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine().trim()); int nodeSize = Integer.parseInt(st.nextToken()); int edgeSize = Integer.parseInt(st.nextToken()); Map graph = new HashMap<>(); for (int i = 0; i < edgeSize; ++i) { st = new StringTokenizer(br.readLine().trim()); int src = Integer.parseInt(st.nextToken()) - 1; int dst = Integer.parseInt(st.nextToken()) - 1; int cost = Integer.parseInt(st.nextToken()); Edge edge; if (graph.containsKey(src)) { edge = graph.get(src); } else { edge = new Edge(); } edge.add(dst, cost); graph.put(src, edge); } int[] dist = new int[nodeSize]; Arrays.fill(dist, Integer.MAX_VALUE); dist[0] = 0; for (int i = 0; i < nodeSize - 1; ++i) { for (Map.Entry entry : graph.entrySet()) { int src = entry.getKey(); Edge edge = entry.getValue(); for (Map.Entry entry2 : edge.edges.entrySet()) { int dst = entry2.getKey(); int cost = entry2.getValue(); int newDist = dist[src] + cost; if (dist[src] != Integer.MAX_VALUE && newDist < dist[dst]) { dist[dst] = newDist; } } } } boolean isNegCyc = false; finalLoop: for (Map.Entry entry : graph.entrySet()) { int src = entry.getKey(); Edge edge = entry.getValue(); for (Map.Entry entry2 : edge.edges.entrySet()) { int dst = entry2.getKey(); int cost = entry2.getValue(); int newDist = dist[src] + cost; if (dist[src] != Integer.MAX_VALUE && newDist < dist[dst]) { isNegCyc = true; break finalLoop; } } } StringBuilder sb = new StringBuilder(); if (isNegCyc) { sb.append(-1); } else { for (int i = 1; i < nodeSize; ++i) { if (dist[i] == Integer.MAX_VALUE) { dist[i] = -1; } sb.append(dist[i]).append("\n"); } } System.out.println(sb.toString()); } }

제출 #141824

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: