ネットワーク・リカバリ

バックアップ2211:ネットワーク・リカバリ

アイデア

問題を見ると最小生成木問題ですか?そうですが、これは1番ノードから出発する際に最小距離を求める問題です.必要なメインラインを全部切るだけで、最後は木になります.各ノードが自分の親ノードのみを記録している場合、どの幹線を使用するべきかを知ることができます.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 1001, INF = 1e9;
int N, M;
vector<pair<int, int>> adj[MAX]; // cost, node
int dist[MAX], prev_node[MAX];
bool visited[MAX];

void dijkstra() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    fill(dist, dist+MAX, INF);
    dist[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        int cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if (visited[cur]) continue;
        visited[cur] = true;
        for (auto p : adj[cur]) {
            int nc = p.first;
            int next = p.second;
            if (visited[next]) continue;
            if (dist[next] > cost+nc) {
                dist[next] = cost+nc;
                prev_node[next] = cur;
                pq.push({cost+nc, next});
            }
        }
    }
}

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

    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >>c;
        adj[a].push_back({c, b});
        adj[b].push_back({c, a});
    }
    dijkstra();
    cout << N - 1;
    for (int i = 2; i <= N; i++) {
        cout << '\n' << i << ' ' << prev_node[i];
    }
    return 0;
}

おしゃべり

問題をよく読みなさい