백준 1916 java - 최소비용 구하기(다익스트라 알고리즘)

문제, 입출력, 테스트케이스

전형적인 다익스트라 문제이다.

 

<소스 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.Array;
import java.util.*;

public class Boj_1916_최소비용구하기 {
    public static void main(String[] args) throws IOException {
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stz;
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        int dist[] = new int[N+1];
        // 거리 초기화
        for (int i = 1; i <= N; i++) {
            dist[i] = 100000000;
        }

        List<int[]>[] v = new ArrayList[N+1];
        for (int i = 0; i <= N; i++) {
            v[i] = new ArrayList<int[]>();
        }

        for (int i = 0; i < M; i++) {
            stz = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(stz.nextToken());
            int to = Integer.parseInt(stz.nextToken());
            int d = Integer.parseInt(stz.nextToken());
            v[from].add(new int[]{to, d});
        }

        stz = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(stz.nextToken());
        int end = Integer.parseInt(stz.nextToken());

        dist[start] = 0;
        pq.offer(new int[]{start, 0});
        while(!pq.isEmpty()){
            int cur[] = pq.poll();

            if(dist[cur[0]] < cur[1])continue;

            for(int i = 0; i < v[cur[0]].size(); i++ ){
                int nxt[] = v[cur[0]].get(i);

                if(dist[nxt[0]] > cur[1] + nxt[1]){
                    dist[nxt[0]] = cur[1] + nxt[1];
                    pq.offer(new int[]{nxt[0], dist[nxt[0]]});
                }
            }
        }

        System.out.print(dist[end]);

    }
}