题意:
给定正边权无向图和起点,求边权和最小的最短路径树
思路:
想象跑一遍 dijkstra 后,对于某边 \(u\to v\) 若 \(d_v \neq d_u+w\)(\(w\) 表示该边的边权),那么这条边不可能在最短路径树上,把它删除
然后用剩下的边做一棵最小生成树就是答案,即每次选择最小的边连接两个连通块。
怎么实现呢?自然可以照着上述说法写一遍,但有更帅的写法
法一:上述方法等价于,在跑 dijkstra 的过程中找到 \(v\) 的最短路中最后一条边的边权最小的那条。即记录到每个点的最短路的最后一条边,当 \(d_v>d_u+w\) 或者 \(d_v=d_u+w\) 且 \(w<last_v\) 时都更新
法二(妙):实际上只需要把 dijkstra 中 if 里面的符号改成大于等于就可以了!这是因为根据 dijkstra 的性质,出队的点的 \(d\) 值是递增的,所以找到的最后一条最短路上的最后一条边就是最小的!
const signed N = 3 + 3e5; int n, m, rt; vector<array<ll,3>> G[N]; //v,w,id int ID[N], W[N]; //最短路径的最后一条边的信息 void sol() { cin >> n >> m; for(int i = 1; i <= m; i++) { int x, y, z; cin >> x >> y >> z; G[x].pb({y,z,i}), G[y].pb({x,z,i}); } cin >> rt; priority_queue<PLL> q; q.push({0,rt}); vector<bool> vis(n+1,0); vector<ll> d(n+1,LLINF); d[rt] = 0; while(q.size()) { int u = q.top().se; q.pop(); if(vis[u]) continue; vis[u] = true; for(auto &[v,w,id]: G[u]) if(d[v] >= d[u] + w) //只需要改成>= d[v] = d[u] + w, ID[v] = id, W[v] = w, q.push({-d[v],v}); } cout << accumulate(W + 1, W + 1 + n, 0ll) << endl; for(int i = 1; i <= n; i++) if(ID[i]) cout << ID[i] << ' '; }