2211번: 네트워크 복구

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


$O(m\lg n)$

1번 지점으로부터 나머지 지점까지의 shortest path로 이뤄진 DAG를 구한다.

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int MXN = 1e3;
int cst[MXN + 1], fr[MXN + 1], n, m;
vector<pair<int, int> > adj[MXN + 1];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, x, y, z; i < m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        adj[x].push_back({ y,z });
        adj[y].push_back({ x,z });
    }
    fill(cst + 2, cst + 1 + n, 1e9);
    priority_queue<pair<int, int> > pq;
    pq.push({ 0,1 });
    printf("%d\n", n - 1);
    while (!pq.empty()) {
        int h = pq.top().second, d = -pq.top().first;
        pq.pop();
        if (cst[h] ^ d) continue;
        if (fr[h]) printf("%d %d\n", fr[h], h);
        for (auto it : adj[h]) if (d + it.second<cst[it.first]) {
            cst[it.first] = d + it.second;
            fr[it.first] = h;
            pq.push({ -cst[it.first],it.first });
        }
    }
    return 0;
}