Prim ~ Dijkstra (BOJ1197 최소 스패닝 트리, BOJ1753 최단경로)

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

1197번: 최소 스패닝 트리

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

int main()
{
    ios_base::sync_with_stdio(false);

    int V, E;
    cin >> V >> E;
    vector<vector<pair<int, int>>> adj(V+1);
    for (int i = 0; i != E; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back(make_pair(c, v));
        adj[v].push_back(make_pair(c, u));
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> selected(V+1);
    long long int total_cost = 0;

    pq.push(make_pair(0, 1));
    while (!pq.empty()) {
        auto [cost, v] = pq.top();
        pq.pop();
        if (selected[v]) {
            continue;
        }
        selected[v] = 1; 
        total_cost += cost;

        for (const auto& p : adj[v]) {
            if (!selected[p.second]) {
                pq.push(p);
            }
        }
    }
    cout << total_cost;

    return 0;
}

==========================================================================================

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

1753번: 최단경로

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using PII = pair<int, int>;

int main()
{   
    ios_base::sync_with_stdio(false);
    
    int V, E;
    cin >> V >> E;
    int source;
    cin >> source;
    
    vector<vector<PII>> adj(V+1);
    for (int i = 0; i != E; ++i) {
        int s, d, w;
        cin >> s >> d >> w;
        adj[s].push_back(make_pair(w, d));
    }

    // Dijkstra using min heap: O(ElogV)
    vector<int> selected(V+1, -1);
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push(make_pair(0, source));
    while (!pq.empty()) {
        const auto [w, v] = pq.top();
        pq.pop();
        if (selected[v] != -1) {
            continue;
        }
        selected[v] = w;
        for (const auto p : adj[v]) {
            if (selected[p.second] == -1) {
                pq.push(make_pair(w + p.first, p.second));
            }
        }
    }

    for (int i = 1; i != V+1; ++i) {
        if (const int cost = selected[i]; cost != -1) {
            cout << cost << '\n';
        } else {
            cout << "INF\n";
        }
    }

    return 0;
}

 

매우 유사하다.

 

차이점:

priority queue의 노드가 다르다. Prim은 해당 edge의 cost를 포함하고, Dijkstra는 path의 total cost를 포함한다.