057 : 최소 비용 구하기

(Briefing)
(문제)	(단 하나의 맥락)	(입출력과 되어야 하는 그림)
N개의 도시 도시 사이의 M개의 버스 특정 구간의 최소 비용 출력		I //  도시 수 N 버스 수 M S도시(1), E도시(1), 버스 비용(1) ... S도시(M), E도시(M), 버스비용(M) 구간 S도시, 구간 E도시 O // 최소 비용 출력

 

import org.w3c.dom.Node;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    // Argument Supply
    static int N, M;
    static ArrayList<Node>[] list;
    static int[] distance;
    static boolean[] visited;

    public static void main(String[] args) throws Exception {

        // Input Supply Cable
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        list = new ArrayList[N+1];
        distance = new int[N+1];
        visited = new boolean[N+1];

        // Preprocessing
        Arrays.fill(distance, Integer.MAX_VALUE);
        for (int i = 0; i <= N; i++) {
            list[i] = new ArrayList<Node>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int fee = Integer.parseInt(st.nextToken());
            list[start].add(new Node(end, fee));
        }

        st = new StringTokenizer(br.readLine());
        int startIndex = Integer.parseInt(st.nextToken());
        int endIndex = Integer.parseInt(st.nextToken());


        // Operating Dijkstra
        bw.write(dijkstra(startIndex, endIndex) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    // External Module Dijkstra
    public static int dijkstra(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        distance[start] = 0;
        while (pq.isEmpty()) {
            Node nowNode = pq.poll();
            int now = nowNode.targetNode;
            if (!visited[now]) {
                visited[now] = true;
                for (Node n : list[now]) {
                    if (!visited[n.targetNode] && distance[n.targetNode] > distance[now] + n.value) {
                        distance[n.targetNode] = distance[now] + n.value;
                        pq.add(new Node(n.targetNode, distance[n.targetNode]));
                    }
                }
            }
        }
        return distance[end];
    }
}

// External Class
class Node implements Comparable<Node> {
    int targetNode;
    int value;
    Node(int targetNode, int value) {
        this.targetNode = targetNode;
        this.value = value;
    }
    @Override
    public int compareTo(Node o) {
        return value - o.value;
    }
}