[알고리즘] 백준 > #1917. 최소비용 구하기

문제링크

백준 #1917. 최소비용 구하기

풀이방법

이 문제는 읽는데 이미 푼 문제인줄 알았습니다.. 혹시 풀었나 확인까지 했어요. 풀고보니 저에 푼 백준 #1753. 최단경로 이 문제와 아주 유사하더라구요! 이 문제도 대표적인 다익스트라 문제입니다~~ 풀이방법이 너무 똑같아서 설명할 것도 없는 거 같네욥.. 입력의 마지막 줄에 주어진 버스의 출발 도시에서 각 도시로 갈 수 있는 최소 비용을 다익스트라 알고리즘을 이용해 구합니다. 다익스트라 알고리즘 구현 시 cost가 작을수록 우선순위가 높은 우선순위큐를 사용했고 버스 정보는 링크드리스트에 저장했습니다~

코드

import java.util.*;

public class BOJ1916 {

    static LinkedList<Bus>[] buses;
    static final int MAX_COST = 100000001;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        buses = new LinkedList[n + 1];
        for (int i = 1; i <= n; i++) buses[i] = new LinkedList<>();

        while (--m >= 0) {
            buses[sc.nextInt()].add(new Bus(sc.nextInt(), sc.nextInt()));
        }

        int srcCity = sc.nextInt();
        int destCity = sc.nextInt();

        boolean[] visited = new boolean[n + 1];
        int[] costs = new int[n + 1];
        for (int i = 1; i <= n; i++) costs[i] = MAX_COST;
        PriorityQueue<MinCost> q = new PriorityQueue<>();
        q.offer(new MinCost(srcCity, 0));
        costs[srcCity] = 0;

        while (!q.isEmpty()) {
            MinCost head = q.poll();

            if (visited[head.src]) continue;

            visited[head.src] = true;
            for (Bus nextBus : buses[head.src]) {
                if (!visited[nextBus.dest]) {
                    costs[nextBus.dest] = Math.min(costs[nextBus.dest], costs[head.src] + nextBus.cost);
                    q.offer(new MinCost(nextBus.dest, costs[nextBus.dest]));
                }
            }
        }

        System.out.print(costs[destCity]);
    }
}

class Bus {
    public int dest;
    public int cost;

    public Bus(int dest, int cost) {
        this.dest = dest;
        this.cost = cost;
    }
}

class MinCost implements Comparable<MinCost> {
    public int src;
    public int cost;

    public MinCost(int src, int cost) {
        this.src = src;
        this.cost = cost;
    }

    @Override
    public int compareTo(MinCost o) {
        return this.cost - o.cost;
    }
}