BOJ 1916 · 최소비용 구하기

알고리즘 분류 : 다익스트라  

A 도시에서 B 도시까지 가는 최단 경로를 구하는 문제다. 도시 간에 비용이 0 이상의 양수 값을 지니므로, 다익스트라 알고리즘을 이용해야 한다.

BOJ 1753번 '최단경로'와 유사한 문제다. 다음 글을 참조.

---

C++ 소스코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

struct bus {
    int city, cost;
    bool operator < (const bus t) const { return cost > t.cost; }
};

int n, m;
int depart, arrive;
const int INF = 1e9;

void dijkstra(vector<bus> a[], int dist[]) {
    priority_queue<bus> pq;
    pq.push({depart, 0});
    dist[depart] = 0;
    while (!pq.empty()) {
        int now = pq.top().city, cost = pq.top().cost;
        pq.pop();
        if (dist[now] < cost) continue;
        for (auto k : a[now]) {
            int next = k.city, ncost = cost+k.cost;
            if (dist[next] > ncost) {
                dist[next] = ncost;
                pq.push({next, ncost});
            }
        }
    }
    cout << dist[arrive] << '\n';
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n;
    cin >> m;
    vector<bus> a[n];
    int dist[n];
    for (int i=0; i<m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        a[u-1].push_back({v-1, w});
    }
    cin >> depart >> arrive;
    depart--, arrive--;
    fill(dist, dist+n, INF);
    dijkstra(a, dist);
    return 0;
}

---

Python 3 소스코드

from heapq import heappush, heappop
from sys import stdin
input = stdin.readline

INF = 1e9
n = int(input())
m = int(input())
dist = [INF]*n
a = [[] for _ in range(n)]
for i in range(m):
    u, v, w = map(int, input().split())
    a[u-1].append([v-1, w])
depart, arrive = map(int, input().split())

def dijkstra():
    pq = []
    heappush(pq, (0, depart-1))
    dist[depart-1] = 0
    while pq:
        cost, now = heappop(pq)
        if dist[now] < cost:
            continue
        for nxt, ncost in a[now]:
            ncost += cost
            if dist[nxt] > ncost:
                dist[nxt] = ncost
                heappush(pq, (ncost, nxt))
    print(dist[arrive-1])

dijkstra()

---

참고

• 백준 온라인 저지 : BOJ 1916
• 최단경로
• 위키피디아 : 데이크스트라 알고리즘