欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ1576: [Usaco2009 Jan]安全路经Travel(最短路 并查集)

程序员文章站 2022-04-18 11:52:37
题意 给你一张无向图,保证从1号点到每个点的最短路唯一。对于每个点求出删掉号点到它的最短路上的最后一条边(就是这条路径上与他自己相连的那条边)后1号点到它的最短路的长度 Sol emmm,考场上想了个贪心开心的飞起然而只多得了10分qwq 正解比较神仙。 首先把最短路树建出来,考虑一条非树边$(u, ......

题意

给你一张无向图,保证从1号点到每个点的最短路唯一。对于每个点求出删掉号点到它的最短路上的最后一条边(就是这条路径上与他自己相连的那条边)后1号点到它的最短路的长度

sol

emmm,考场上想了个贪心开心的飞起然而只多得了10分qwq

正解比较神仙。

首先把最短路树建出来,考虑一条非树边$(u, v)$什么时候能更新答案

结论是:除了他们的lca外的子树内其他都可以更新,且新的权值为$dis[u] + dis[v] + w(u, v) - dis[x]$,$x$表示新节点

这样我们把所有的边按照$dis[u] + dis[v] + w(u, v)$排序,显然,一个点如果被更新过那么就再也不会被更新了。

用并查集把已经更新过的点缩起来即可

 

这题的关键是要发现非树边与答案之间的性质。。

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
#define pair pair<int, int> 
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
const int maxn = 1e6 + 10, inf = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m;
vector<pair> v[maxn];
struct edge {
    int u, v, w;
}e[maxn];
int num = 0;
int dis[maxn], top[maxn], vis[maxn], cnt = 0, ans[maxn];
void dij() {
    memset(dis, 0x7f, sizeof(dis));
    dis[1] = 0;
    priority_queue<pair> q; q.push(mp(0, 1));
    while(!q.empty()) {
        int p = q.top().se; q.pop();
        if(vis[p]) continue; vis[p] = 1;
        for(int i = 0; i < v[p].size(); i++) {
            int to = v[p][i].fi, w = v[p][i].se;
            if(dis[to] > dis[p] + w && (!vis[to])) {
                top[to] = p;
                dis[to] = dis[p] + w;
                q.push(mp(-dis[to], to));
            }
        }
    }
}
int comp(const edge &a, const edge &b) {
    return dis[a.u] + dis[a.v] + a.w < dis[b.u] + dis[b.v] + b.w;
}
int fa[maxn];
int unionn(int x, int y) {
    fa[x] = y;
}
int find(int x) {
    if(fa[x] == x) return fa[x];
    else return fa[x] = find(fa[x]);
}
int solve(int x, int y, int w) {
    while((x = find(x)) != (y = find(y))) {
        //int dx = dis[x], dy = dis[y];
        if(dis[x] < dis[y]) swap(x, y);
        ans[x] = w - dis[x];
        x = (fa[x] = top[x]);
        cnt++;
    }
}
int main() {
    n = read(); m = read();    
    for(int i = 1; i <= m; i++) {
        int x = read(), y = read(), z = read();
        v[x].push_back(mp(y, z));
        v[y].push_back(mp(x, z));
    }
    dij();
    for(int i = 1; i <= n; i++) {
        fa[i] = i;
        for(int j = 0; j < v[i].size(); j++) {
            int to = v[i][j].fi, w = v[i][j].se;
            if(top[to] == i || top[i] == to) continue;
            e[++num] = (edge) {i, to, w};
        }
    }
    sort(e + 1, e + num + 1, comp);
    for(int i = 1; i <= num; i++) {
        solve(e[i].u, e[i].v, dis[e[i].u] + dis[e[i].v] + e[i].w);
        if(cnt == n - 1) break;
    }
    for(int i = 2; i <= n; i++)
        printf("%d\n", ans[i] ? ans[i] : -1);
    return 0;
}