并查集: 按权值排序,暴力更新;每次记录一个祖先: 从没有被更新的开始更新
点击查看代码
</details>
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = 4005, M = 5e5 + 5;
int n, m;
int h[N], e[N << 1], w[N << 1], nxt[N << 1], idx;
struct E { int a, b, c; } edges[M]; int tot; // 非树边
int dist[N], fa[N], father[N];
int from[N];
void add(int a, int b, int c) {
e[++ idx] = b, w[idx] = c, nxt[idx] = h[a], h[a] = idx;
}
void dfs(int u) {
for(int i = h[u]; i; i = nxt[i]) {
int v = e[i];
if(v == fa[u]) continue;
dist[v] = dist[u] + w[i], fa[v] = u;
dfs(v);
}
}
int find(int x) {
if(x == father[x]) return x;
return father[x] = find(father[x]);
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1, a, b, c, t; i <= m; i ++) {
scanf("%d%d%d%d", &a, &b, &c, &t);
if(t) add(a, b, c), add(b, a, c);
else edges[++ tot] = {a, b, c};
}
dfs(1);
for(int i = 1; i <= tot; i ++)
edges[i].c += dist[edges[i].a] + dist[edges[i].b];
std::sort(edges + 1, edges + tot + 1, [](const E&a, const E&b) { return a.c < b.c; });
for(int i = 1; i <= n; i ++) father[i] = i;
for(int i = 1; i <= tot; i ++) {
int x = find(edges[i].a), y = find(edges[i].b);
while(x != y) {
if(dist[x] < dist[y]) x ^= y ^= x ^= y;
if(!from[x]) from[x] = i; // 被更新了
x = fa[x] = find(fa[x]); // 暴力向上跳
}
}
for(int i = 2; i <= n; i ++)
if(from[i]) printf("%d ", edges[from[i]].c - dist[i]);
else printf("-1 ");
return 0;
}