道路削减｜最短路生成树

第五题 - A24634.道路削减

题目链接跳转：A24634.道路削减

前言：刚开始看这道题目的时候看成了最小生成树的模板题目，盲目的 wsq 随手打了一篇最小生成树的代码交上去，荣获满堂红（葬送了好多次提交记录，真是个悲惨的事情）。

最短路树的模板题目，在 Dijkstra 求最短路径的基础上，记录每一个顶点的“前驱边”就行了。更进一步地，如果松弛了某一条边 $E(A, B)$，可以使得从源点到达 $B$ 点的最短距离缩短，那么就保留这一条边（覆盖掉原本通往 $B$ 点的前驱边即可，一开始没有可以设置为无穷大或者是一个无意义的数字）。可以证明，如果有 $N$ 个顶点，排除源点，当每一个顶点都有一个前驱边时，图上正好只有 $N-1$ 条边。且每一个点到源点的距离都是最小的。

PS：本题的数据量比较大，一定要开 long long 数据类型，同时在计算最短路初始化的时候，切记无穷大要开的大一点。

本题的 AC 代码如下：

#include <iostream>
#include <queue>
#include <algorithm>
#include <unordered_map>
#define int unsigned long long
using namespace std;

const int M = 2e5 + 10;
int n, m, ei, vertex[M];
struct node{
    int to, next;
    int weight, id;
} edges[M * 2]; 
struct Node {
    int vertex, distance;
    bool operator>(const Node& other) const {
        return distance > other.distance;
    }
};
int dis[M], fa[M], road[M];

void add(int v1, int v2, int weight, int id){
    ei += 1;
    edges[ei].to = v2;
    edges[ei].weight = weight;
    edges[ei].next = vertex[v1];
    edges[ei].id = id;
    vertex[v1] = ei;
}

void dijkstra(){
    for (int i=1; i<=n; i++){
        dis[i] = 1e15;
        fa[i] = -1;
    }
    dis[1] = 0;
    priority_queue<Node, vector<Node>, greater<Node>> que;
    que.push((Node){1, 0});
    while(que.size()){
        Node t = que.top();
        que.pop();
        int u = t.vertex;
        if (t.distance > dis[u]) continue;
        for (int index=vertex[u]; index; index=edges[index].next){
            int v = edges[index].to;
            int weight = edges[index].weight;
            if (dis[u] + weight < dis[v]){
                dis[v] = dis[u] + weight;
                fa[v] = u; 
                road[v] = edges[index].id;
                que.push((Node){v, dis[v]});
            }
        }
    }
    return ;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i=1, u, v, w; i<=m; i++){
        cin >> u >> v >> w;
        add(u, v, w, i); add(v, u, w, i);
    }
    dijkstra();
    for (int i=1; i<=n; i++) {
        if (i != 1 && fa[i] != -1) {
            cout << road[i] << " ";
        }
    }
    return 0;
}