[백준] 최소비용 구하기 - Gold 5

[jusung-c]

문제 링크

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

문제 조건

• N(1 ≤ N ≤ 1,000)개의 도시가 있을 때 한 도시에서 출발해 다른 도시에 도착하는 M(1 ≤ M ≤ 100,000)개의 버스가 있다.
• A번째 도시에서 B번째 도시까지 가는 데 최소비용을 구하라

---

아이디어

버스 비용은 모두 0 이상이고, 시작점과 도착점이 주어지므로 다익스트라 알고리즘을 적용하면 최단거리를 구할 수 있다.

최단 거리의 특성

• 같은 정점을 두 번 방문할 이유가 없다. -> 사이클은 절대 최단 거리가 아니다.
• 따라서 정답은 최대 버스 비(10만) * 정점 수(1천) = 1억으로 int로 충분하다.

1. 간선의 정보를 그래프로 표현한다.
2. 시작점부터 다익스트라 알고리즘을 적용한다.
   1. dist 배열 초기화 및 시작점을 큐에 넣는다.
   2. 큐가 빌때까지 아래 과정을 반복한다.
   3. 가장 d가 작은 노드를 추출하고, dist값과 비교해 가치를 판단한다.
   4. 가치가 있는 경우 연결된 간선들의 정보를 활용해 다음 정점까지의 거리와 dist 값을 비교해 가치를 판단한다.
   5. 가치가 있는 경우 dist값을 갱신하고 큐에 해당 정보를 넣는다.

---

시간 복잡도

O(E logV)이므로 시간 안 풀이가 가능하다.

---

구현

import java.io.*;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));;
    static StringTokenizer st;
    static int N, M, start, end;
    static int[] dist;
    static ArrayList<Edge>[] edges;
    static class Edge {
        int to, weight;

        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
    static class Info {
        int idx, dist;

        public Info(int idx, int dist) {
            this.idx = idx;
            this.dist = dist;
        }
    }

    public static void init() throws IOException {
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        edges = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) edges[i] = new ArrayList<>();

        dist = new int[N + 1];

        for (int i=1; i<=M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            edges[from].add(new Edge(to, weight));
        }

        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
    }

    private static void pro() throws IOException {
        dijkstra(start);

//        for (int i=1; i<=N; i++) {
//            bw.write(dist[i] + " ");
//        }
//        bw.newLine();
        bw.write(dist[end] + " ");
    }

    private static void dijkstra(int start) {
        // dist 배열 초기화 및 시작점 큐에 넣기
        for (int i=1; i<=N; i++) {
            if (i == start) dist[i] = 0;
            else dist[i] = Integer.MAX_VALUE;
        }

        PriorityQueue<Info> que = new PriorityQueue<>((o1, o2) -> o1.dist - o2.dist);
        que.add(new Info(start, 0));

        // 큐가 빌 때까지 반복
        while (!que.isEmpty()) {
            // 가장 d가 작은 노드 추출
            Info info = que.poll();

            // 가치가 있는지 판단
            if (dist[info.idx] < info.dist) continue;

            // 연결된 간선들 확인
            for (Edge e : edges[info.idx]) {
                // 간선의 정보가 가치가 있는지 판단
                if (dist[info.idx] + e.weight >= dist[e.to]) continue;

                // 최단거리 갱신 후 큐에 넣기
                dist[e.to] = dist[info.idx] + e.weight;
                que.add(new Info(e.to, dist[e.to]));
            }
        }
    }

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

        pro();

        bw.close();
    }
}