import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { timeMachine(); } public static class City { List nextList; // to, cost public City(int to, int cost) { nextList = new ArrayList<>(); nextList.add(new int[]{to, cost}); } public void addNext(int to, int cost) { nextList.add(new int[]{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) { List nextList = city[curr].nextList; for (int[] next : nextList) { int nextCity = next[0]; int nextCost = next[1]; 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]) { recursive(city, cycleMap, visit, min, nextSum, nextCity); } else { if (nextSum < min[nextCity]) { recursive(city, cycleMap, visit, min, nextSum, nextCity); } } } } } } }

제출 #136380

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: