import java.util.*; import java.io.*; public class Main { static class Road implements Comparable{ int to; int cows; Road(int to, int cows) { this.to = to; this.cows = cows; } @Override public int compareTo(Road o) { return o.cows - this.cows; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); // 헛간의 개수 (N = 찬홍이의 위치) int M = Integer.parseInt(st.nextToken()); // 소들의 길의 개수 (양방향 길) ArrayList> roads = new ArrayList<>(); for (int i = 0; i < N; i++) { roads.add(new ArrayList<>()); } for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); int from = Integer.parseInt(st.nextToken()); int to = Integer.parseInt(st.nextToken()); int cows = Integer.parseInt(st.nextToken()); roads.get(from).add(new Road(to, cows)); } boolean[] visited = new boolean[N+1]; int[] dist = new int[N+1]; for (int i = 0; i < N+1; i++) { dist[i] = Integer.MAX_VALUE; } dist[1] = 0; for (int i = 0; i < N; i++) { int nowValue = Integer.MAX_VALUE; int now = 0; for (int j = 1; j < N+1; j++) { if (visited[j] && dist[j] < nowValue) { nowValue = dist[j]; now = j; } } visited[now] = true; for (int j = 0; j < roads.get(now).size; j++) { Road adjRoad = roads.get(now).get(j); if (dist[adjRoad.to] > dist[now] + adjRoad.cows) { dist[adjRoad.to] = dist[now] + adjRoad.cows; } } } int sum = 0; for (int i = 1; i < N+1; i++) { if (dist[i] != Integer.MAX_VALUE) { sum += dist[i]; } } System.out.println(sum); } }

제출 #161052

제출 정보

제출 결과

제출 코드

찾은 반례