백준 1753번: 최단경로(Python, cpp)

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

1753번: 최단경로

---

문제 해결을 위한 과정

다익스트라 알고리즘을 이용하여 해결할 수 있는 문제였습니다. 다익스트라 기본 코드를 정확하게 알고 있다면 매우 쉽게 해결할 수 있었습니다.

---

소스코드 - python

import heapq, sys
input = sys.stdin.readline
INF = int(1e9)
 
 
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
 
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
                
v, e = map(int, input().split())
start = int(input())
graph = [[] for _ in range(v+1)]
distance = [INF] * (v+1)
 
for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
 
dijkstra(start)
 
for i in range(1, v+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])
 

---

소스코드 - c++

#include <bits/stdc++.h>
#define MAX 20001
#define INF (int)1e9
using namespace std;
vector<pair<int, int> > graph[MAX];
int d[MAX];
int v, e;
 
void dijkstra(int start) {
    priority_queue<pair<int, int> > pq;
    pq.push({ 0, start });
    d[start] = 0;
 
    while (!pq.empty()) {
        int dist = -pq.top().first;
        int now = pq.top().second;
        pq.pop();
        if (d[now] < dist)
            continue;
        for (int i = 0; i < (signed)graph[now].size(); i++) {
            int cost = dist + graph[now][i].second;
            if (cost < d[graph[now][i].first]) {
                d[graph[now][i].first] = cost;
                pq.push({ -cost, graph[now][i].first });
            }
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> v >> e;
    int start;
    cin >> start;
    fill(d, d + MAX, INF);
 
    for (int i = 0; i < e; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
    }
 
    dijkstra(start);
 
    for (int i = 1; i <= v; i++) {
        if (d[i] == INF) {
            cout << "INF" << "\n";
        }
        else {
            cout << d[i] << "\n";
        }
    }
    return 0;
}