SPFA 算法

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

const int N = 10010, M = 2e5 + 10, INF = 0x3f3f3f3f;

int n, m;
struct Edge {
    int to;     // 终点城市
    int weight; // 铁路的权重（长度）
};

vector<Edge> adj[N]; // 使用 vector 来存储每个城市的邻接表
int dist[N];          // 最短路径数组
bool st[N];           // 队列标记数组

// SPFA 算法求最短路径
void spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;  // 首都的最短距离为 0
    queue<int> q;
    q.push(1);
    st[1] = true;

    while (!q.empty()) {
        int t = q.front(); q.pop();
        st[t] = false;

        // 遍历当前城市t的所有邻接城市
        for (auto& edge : adj[t]) {
            int j = edge.to;
            if (dist[j] > dist[t] + edge.weight) {
                dist[j] = dist[t] + edge.weight;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;

    // 输入并构建邻接表
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});  // 向城市a的邻接表中添加一条铁路
        adj[b].push_back({a, c});  // 由于是无向图，每条铁路要双向添加
    }

    // 执行 SPFA 算法
    spfa();

    // 计算满足条件的最小改造铁路长度
    int res = 0;
    for (int a = 2; a <= n; a++) {
        int minw = INF;
        // 遍历每个城市的邻接城市，找到满足条件的最小权重边
        for (auto edge : adj[a]) {
            int b = edge.to;
            if (dist[a] == dist[b] + edge.weight) {
                minw = min(minw, edge.weight);
            }
        }
        res += minw;
    }

    cout << res << endl;
    return 0;
}