import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { timeMachine(); } public static class City { Map nextMap; // to, cost; public City(int to, int cost) { nextMap = new HashMap<>(); nextMap.put(to, cost); } public void addNext(int to, int cost) { if (nextMap.containsKey(to)) { int value = nextMap.get(to); if (cost < value) { nextMap.replace(to, cost); } } else { nextMap.put(to, cost); } } } public static void timeMachine() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine().trim()); int citySize = Integer.parseInt(st.nextToken()); int lineSize = Integer.parseInt(st.nextToken()); City[] city = new City[citySize + 1]; for (int i = 0; i < lineSize; ++i) { st = new StringTokenizer(br.readLine().trim()); int from = Integer.parseInt(st.nextToken()); int to = Integer.parseInt(st.nextToken()); int cost = Integer.parseInt(st.nextToken()); if (city[from] == null) { city[from] = new City(to, cost); } else { city[from].addNext(to, cost); } } boolean[] visit = new boolean[citySize + 1]; int[] min = new int[citySize + 1]; min[1] = 0; Arrays.fill(min, Integer.MAX_VALUE); Map cycleMap = new HashMap<>(); recursive(city, cycleMap, visit, min, 0, 1); for (int i = 2; i < citySize + 1; ++i) { if (!visit[i]) { min[i] = -1; } } StringBuilder sb = new StringBuilder(); if (ans == 0) { for (int i = 2; i < citySize + 1; ++i) { sb.append(min[i]).append("\n"); } } else { sb.append(ans); } System.out.println(sb.toString()); } public static class Cycle { int sAccCost; public Cycle(int sAccCost) { this.sAccCost = sAccCost; } public boolean checkCycle(int eAccCost) { return eAccCost - sAccCost < 0; } } public static int ans = 0; public static void recursive(City[] city, Map cycleMap, boolean[] visit, int[] min, int sum, int curr) { visit[curr] = true; min[curr] = Math.min(min[curr], sum); if (city[curr] != null) { Map nextMap = city[curr].nextMap; for (Map.Entry entry : nextMap.entrySet()) { int nextCity = entry.getKey(); int nextCost = entry.getValue(); int nextSum = sum + nextCost; boolean nextCycle = nextCost < 0; if (nextCycle) { if (cycleMap.containsKey(nextCity)) { Cycle cycle = cycleMap.get(nextCity); if (cycle.checkCycle(nextSum)) { ans = -1; } } else { cycleMap.put(nextCity, new Cycle(nextSum)); if (nextSum < min[nextCity]) { recursive(city, cycleMap, visit, min, nextSum, nextCity); } } } else { if (!visit[nextCity] || nextSum < min[nextCity]) { recursive(city, cycleMap, visit, min, nextSum, nextCity); } } } } } }

제출 #136454

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: