greentea31's Note

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

풀이 과정

방향 그래프를 줄 테니 시작점에서 다른 모든 정점으로의 최단 경로를 구하라는 문제다. 가중치가 자연수라는 조건이 중요하다.

그래프에서 최단 경로를 찾으라고 하면 BFS, 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘이 떠오르는데, 나열한 알고리즘에서 왼쪽으로 갈수록 빠른 알고리즘이지만, 더욱 특수한 조건에서만 사용이 가능하다.

BFS는 모든 간선의 가중치가 1이어야 하고, 다익스트라는 모든 간선의 가중치에 음수가 존재하면 안 된다, 벨만-포드나 플로이드-워셜 알고리즘은 간선의 가중치에 상관없이 사용이 가능하지만 알고리즘이 돌아가는데 더욱 오랜 시간이 걸린다.

이 문제는 가중치가 자연수로 주어지므로 다익스트라 알고리즘을 사용하여 최단 경로를 구할 수 있다.

소스 코드

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

const int INF = 987654321;
int d[20005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int V, E, u, v, w;
    cin >> V >> E;

    for (int i = 1; i < V+1; i++) { // 무한대 초기화
        d[i] = INF;
    }

    int start;
    cin >> start;

    vector<pair<int, int>> adj[20005];

    for (int i = 0; i < E; i++) { // 인접 리스트
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(w, v));
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 최소 힙
    d[start] = 0;
    pq.push(make_pair(d[start], start)); // 시작 거리 0 최소화후 최소힙 삽입


    while(!pq.empty()) {
        pair<int, int> cur = pq.top(); pq.pop();
        if (d[cur.second] != cur.first) continue;
        for (int i = 0; i < adj[cur.second].size(); i++) {
            pair<int, int> next = adj[cur.second][i];
            if (d[next.second] <= d[cur.second] + next.first) continue;
            d[next.second] = d[cur.second] + next.first;
            pq.push(make_pair(d[next.second], next.second));
        }
    }

    for (int i = 1; i < V+1; i++) {
        if (d[i] == INF) cout << "INF\n";
        else cout << d[i] << '\n';
    }

    return 0;
}