[BJ] 1916 : 최소비용 구하기

       문제 요약        

 

 

 

 

 

         아이디어        

다익스트라

 

 

 

         소스코드        

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

public class Main {// 최소비용 구하기
    //다익스트라
    static int N, M; // 도시의 개수, 버스의 개수
    static List<Node>[] adjList;
    static int[] dist;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 도시의 개수
        M = Integer.parseInt(br.readLine()); // 버서의 개수
        adjList = new ArrayList[N + 1];
        for(int n=0;n<N+1;n++){
            adjList[n] = new ArrayList<>();
        }
        StringTokenizer st;
        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            adjList[a].add(new Node(b, cost));
        }
        // 출발점 도시번호 ~ 도착점 도시번호
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        dist = new int[N+1];
        Arrays.fill(dist,Integer.MAX_VALUE);
        dijkstra(start,end);
    }
    private static void dijkstra(int start, int end){
        boolean[] visited = new boolean[N+1];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start,0));
        dist[start] = 0;
        while(!pq.isEmpty()){
            Node now = pq.poll(); // 가장 가까운 노드 선택
            if(visited[now.to])continue;
            visited[now.to] = true;
            for(Node next: adjList[now.to]){ // 선택된 노드와 연결되어있는 노드들에 대해
                if(dist[next.to]>dist[now.to]+next.cost){ //  
                    dist[next.to] = dist[now.to]+next.cost;
                    pq.add(new Node(next.to,dist[next.to]));
                }
            }
        }
        System.out.println(dist[end]);
    }
    static class Node implements Comparable<Node> {
        int to, cost;
        public Node(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }
        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }
}