USACO安全路径_usaco】安全路经

这题是道神题，虽然考试时并没有时间去看这道题目

由于是牛i从牛棚1到牛棚i的路径是一样的
我们可以证明：可以生成一个最小路径树

同时还可得出一个定理：使变化后的路径最优，那么最多添加一条边

设我们添加一条长度为len，连接x和y的边
那么它会构成一个环，且这个环的其他点都存在与x与y到其最近公共祖先的路径上（设这个环上的点为a）。
这时到这些点的路径即可更新，新的路径为newdis[a]=dis[x]+dis[y]+len-dis[a];
如果这样纯暴力，复杂度为n*m（虽然可以过-_-）

优化
一个点可能被很多环所包含，这样就要不断更新，但如果我们可以每个点只更新一次，复杂度下降很多
可以发现，对于一个点，他的最新路径只与它的原来路径与dis[x]+dis[y]+len有关
如果我们能保证dis[x]+dis[y]+len最小，那么被更新的路径一定是最小的
所以我们可以根据（dis[x]+dis[y]+len）从小到大排序，把环内的点更新一次就好
为了使每个点只被更新一次，那么我们可以使用并查集进行路径压缩

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define FOR(i,x,y) for(int i=(x);i<=(y);i++)
#define DOR(i,x,y) for(int i=(x);i>=(y);i--)
#define M 200005
#define pb push_back
struct path{int x,y,z;}L[M];//记录每条边
struct node{int to,v;};
vector<node>edge[M];
typedef pair<int,int>P;
P E[M]; 
int fa[M],dep[M],Fa[M];
int dis[M],ans[M];
struct shortpath{
    priority_queue<P,vector<P>,greater<P> >q;
    void dj(){//迪杰斯特拉算最短路，听说这题卡spfa 
        memset(dis,63,sizeof(dis));
        dis[1]=0;
        q.push(P(0,1));
        while(!q.empty()){
            P p=q.top();q.pop();
            int v=p.second;
            if(dis[v]<p.first)continue;
            for(unsigned int i=0;i<edge[v].size();i++){
                int x=edge[v][i].to;
                if(dis[x]>dis[v]+edge[v][i].v){
                    dis[x]=dis[v]+edge[v][i].v;
                    q.push(P(dis[x],x));
                }
            }
        }
    }
    void make(int x,int f,int l){//生成最短路径树 
        fa[x]=f;
        dep[x]=dep[f]+1;
        for(unsigned int i=0;i<edge[x].size();i++){
            int y=edge[x][i].to;
            if(dis[y]==dis[x]+edge[x][i].v){
                make(y,x,edge[x][i].v);
            }
        }
    }
    int find(int x){return x==Fa[x]?x:Fa[x]=find(Fa[x]);}
    void UP(int x,int y,int len){
        while(x!=y){
            if(dep[x]>dep[y]){
                if(ans[x]==-1)ans[x]=len-dis[x];
                Fa[x]=fa[x];
                x=find(x);
            }
            else {
                if(ans[y]==-1)ans[y]=len-dis[y];
                Fa[y]=fa[y];
                y=find(y);
            }
        }
    }
    void deal(int m,int n){
        memset(ans,-1,sizeof(ans));
        int cnt=0;
        FOR(i,1,n)Fa[i]=i;//初始化并查集 
        FOR(i,1,m){//找到非最短路径上的边 
            if((dis[L[i].x]==dis[L[i].y]+L[i].z)||(dis[L[i].y]==dis[L[i].x]+L[i].z))continue;
            int x=L[i].x,y=L[i].y;
            E[++cnt]=P(dis[x]+dis[y]+L[i].z,i);
        }
        sort(E+1,E+cnt+1); 
        FOR(i,1,cnt){
            int x=L[E[i].second].x,y=L[E[i].second].y;
            UP(x,y,E[i].first); 
        }
    }
}T;
int main(){
    int n,m,x,y,z;
    cin>>n>>m;
    FOR(i,1,m){
        scanf("%d%d%d",&x,&y,&z);
        L[i].x=x,L[i].y=y,L[i].z=z; 
        edge[x].pb((node){y,z});
        edge[y].pb((node){x,z});
    }
    T.dj();
    T.make(1,0,0);
    T.deal(m,n);
    FOR(i,2,n)printf("%d\n",ans[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93