#백준_1916 최소비용 구하기 - Java 자바

#유형: 최단경로, 다익스트라

#난이도: 골드 V

# 우선순위큐를 바탕으로 다익스트라 알고리즘을 구현하면 된다. 보통  A번째 도시에서 B번째 도시까지 가는데 드는 최소비용은 최단거리 문제이며, 정점을 기준으로 다익스트라인지 플로이드와샬인지, 음수 포함여부에 따라 벨만포드 등으로 나뉘어진다.

이 문제는 다익스트라 문제이며, 우선순위큐를 이용해 풀었고 주석을 달아놓았다.

 

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class p1916 {
    static int N,M;
    static ArrayList<Point>[] arrList;
    static int dist[];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        arrList = new ArrayList[N+1];
        dist = new int[N+1];
        for(int i=1; i<=N; i++)
            dist[i] = 987654321;
        for(int i=1; i<=N; i++) {
            arrList[i] = new ArrayList<>();
        }
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            arrList[u].add(new Point(v, value));
        }
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        solve(start);
        System.out.println(dist[end]);
    }
    
    public static void solve(int start) {
        PriorityQueue<Point> pq = new PriorityQueue<>();
        pq.add(new Point(start, 0));
        dist[start] = 0;
        
        while(!pq.isEmpty()) {
            Point po = pq.poll();
            if(dist[po.x] < po.y)
                continue;
            
            // 현재 인덱스와 연결 된 모든 버스 확인
            for(int i=0; i<arrList[po.x].size(); i++) {
                Point p = arrList[po.x].get(i);
                // start 에서 p.x 도시 까지 가는 최단거리 갱신
                if(dist[p.x] > dist[po.x] + arrList[po.x].get(i).y) {
                    dist[p.x] = dist[po.x] + arrList[po.x].get(i).y;
                    pq.add(new Point(p.x, dist[p.x]));
                }
            }
        }
        
    }
    
    
    public static class Point implements Comparable<Point>{
        int x;
        int y;
        public Point(int x, int y) {
            this.x=x;
            this.y=y;
        }
        // 우선순위큐에서 가까운 값이 우선순위로 계산되게 하는 
        @Override
        public int compareTo(Point o) {
            if(this.y - o.y < 0)
                return 1;
            else
                return 0;
        }
    }
}