백준 5972

●문제 출처

https://www.acmicpc.net/problem/5972

●정리(요약)
농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.

농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <= 1,000) 마리의 소가 있습니다. 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i)를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.

다음 지도를 참고하세요.

    [2]---
      / |    \
     /1 |     \ 6
    /   |      \
 [1]   0|    --[3]
    \   |   /     \2
    4\  |  /4      [6]
      \ | /       /1
       [4]-----[5] 
            3  
            

농부 현서가 선택할 수 있는 최선의 통로는 1 -> 2 -> 4 -> 5 -> 6 입니다. 왜냐하면 여물의 총합이 1 + 0 + 3 + 1 = 5 이기 때문입니다.

농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야할 여물의 비용이 주어질 때 최소 여물은 얼마일까요? 농부 현서는 가는 길의 길이는 고려하지 않습니다.

●코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int[] dist;
    static List<Cow>[] list;
    static boolean[] visited;

    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());
        int M = Integer.parseInt(st.nextToken());

        dist = new int[N + 1];
        visited = new boolean[N + 1];
        list = new ArrayList[N + 1];

        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
            dist[i] = Integer.MAX_VALUE;
        }
        dist[1] = 0;

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            list[A].add(new Cow(B, C));
            list[B].add(new Cow(A, C));
        }

        PriorityQueue<Cow> pq = new PriorityQueue<>();
        pq.offer(new Cow(1, 0));

        while (!pq.isEmpty()) {
            Cow now = pq.poll();

            if (visited[now.end]) {
            	continue;
            }
            
            visited[now.end] = true;

            for (Cow next : list[now.end]) {
                if (!visited[next.end] && dist[next.end] > dist[now.end] + next.cnt) {
                    dist[next.end] = dist[now.end] + next.cnt;
                    pq.offer(new Cow(next.end, dist[next.end]));
                }
            }
        }

        System.out.println(dist[N]);
    }

    static class Cow implements Comparable<Cow> {
        int end;
        int cnt;

        public Cow(int end, int cnt) {
            this.end = end;
            this.cnt = cnt;
        }

        @Override
        public int compareTo(Cow o) {
            return this.cnt - o.cnt;
        }
    }
}

●느낀 점

다익스트라!!

양방향이라
list[A].add(new Cow(B, C));
list[B].add(new Cow(A, C));
해주었고

Comparable 의 compareTo 하여 작은 순으로 정렬되도록 하여 dist[next.end] > dist[now.end] + next.cnt인 값을 우선순위 큐에 담아 dist[N] 의 값을 구하였습니다.