【bzoj1576/Usaco2009 Jan】安全路经Travel——dijkstra+并查集

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<queue>
 5 #define mem(a,p) memset(a,p,sizeof(a))
 6 const int N=1e5+10,M=2e5+10;
 7 using std::swap;
 8 using std::sort;
 9 struct node{int fr,to,ne,w;}e[M*2],d[M*2];
10 struct point{
11     int d,id;
12     bool operator <(const point&p)const {return p.d<d;}
13 };
14 int n,an[N],m,first[N],dis[N],tot=0,fa[N],dep[N],cnt=0;
15 std::priority_queue<point>q;
16 int read(){
17     int ans=0,f=1;char c=getchar();
18     while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
19     while(c>=‘0‘&&c<=‘9‘){ans=ans*10+c-48;c=getchar();}
20     return ans*f;
21 }
22 bool cmp(node a,node b){return a.w<b.w;}
23 void ins(int u,int v,int w){e[++tot]=(node){u,v,first[u],w};first[u]=tot;}
24 void dijkstra(){
25     mem(dis,127);dis[1]=0;q.push((point){0,1});
26     while(!q.empty()){
27         point p=q.top();q.pop();
28         int x=p.id;
29         for(int i=first[x];i;i=e[i].ne){
30             int to=e[i].to;
31             if(dis[to]>dis[x]+e[i].w){
32                 dis[to]=dis[x]+e[i].w;q.push((point){dis[to],to});
33                 dep[to]=dep[x]+1;
34                 fa[to]=x;
35             }
36         }   
37     }
38 }
39 int f[N],ans[N];
40 int getf(int x){
41     if(f[x]==x)return x;
42     f[x]=getf(f[x]);
43     return f[x];
44 }
45 int main(){
46     n=read();m=read();
47     for(int i=1;i<=n;i++)f[i]=i;
48     for(int i=1,a,b,c;i<=m;i++){
49         a=read();b=read();c=read();ins(a,b,c);ins(b,a,c);
50     }
51     dijkstra();
52     for(int i=1;i<=tot;i++){
53         int x=e[i].fr,y=e[i].to;
54         if(dep[x]<dep[y])swap(x,y);
55         if(dis[x]==dis[y]+e[i].w)continue;
56         d[++cnt]=(node){x,y,0,e[i].w+dis[x]+dis[y]};
57     }
58     sort(d+1,d+1+cnt,cmp);
59     for(int i=1;i<=cnt;i++){
60         int x=d[i].fr,y=d[i].to;
61         x=getf(x),y=getf(y);
62         while(x!=y){
63             if(dep[x]<dep[y])swap(x,y);
64             if(!ans[x])ans[x]=d[i].w-dis[x];
65             x=f[x]=getf(fa[x]);
66         }
67     }
68     for(int i=2;i<=n;i++){
69         if(!ans[i])printf("-1\n");
70         else printf("%d\n",ans[i]);
71     }
72     return 0;
73 }
74