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

Description

Input

* 第一行: 两个空格分开的数, N和M

* 第2..M+1行: 三个空格分开的数a_i, b_i,和t_i

Output

* 第1..N-1行: 第i行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.

Sample Input

4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3
输入解释:

跟题中例子相同

Sample Output

3
3
6
输出解释:

跟题中例子相同

 

---

 

先跑一遍dijkstra求出每个点的dis和在最短路树中的dep及fa，

然后枚举所有非树边->由图（自己画去）易证不经过最后一条边的最短路一定最多只经过一条非树边。

若我们的源点为S，终点为T，可以发现如果走一条非树边答案为dis[fr]+dis[to]-dis[T]+e[i].w，观察式子可以发现dis[T]至于每个点自身有关，因此可以把dis[fr]+dis[to]+e[i].w作为非树边的权值。

将非树边按权值从小到大排序，尝试更新fr和to到lca的答案，并查集来实现跳转。

具体实现方式看代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define mem(a,p) memset(a,p,sizeof(a))
const int N=1e5+10,M=2e5+10;
using std::swap;
using std::sort;
struct node{int fr,to,ne,w;}e[M*2],d[M*2];
struct point{
    int d,id;
    bool operator <(const point&p)const {return p.d<d;}
};
int n,an[N],m,first[N],dis[N],tot=0,fa[N],dep[N],cnt=0;
std::priority_queue<point>q;
int read(){
    int ans=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-48;c=getchar();}
    return ans*f;
}
bool cmp(node a,node b){return a.w<b.w;}
void ins(int u,int v,int w){e[++tot]=(node){u,v,first[u],w};first[u]=tot;}
void dijkstra(){
    mem(dis,127);dis[1]=0;q.push((point){0,1});
    while(!q.empty()){
        point p=q.top();q.pop();
        int x=p.id;
        for(int i=first[x];i;i=e[i].ne){
            int to=e[i].to;
            if(dis[to]>dis[x]+e[i].w){
                dis[to]=dis[x]+e[i].w;q.push((point){dis[to],to});
                dep[to]=dep[x]+1;
                fa[to]=x;
            }
        }   
    }
}
int f[N],ans[N];
int getf(int x){
    if(f[x]==x)return x;
    f[x]=getf(f[x]);
    return f[x];
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1,a,b,c;i<=m;i++){
        a=read();b=read();c=read();ins(a,b,c);ins(b,a,c);
    }
    dijkstra();
    for(int i=1;i<=tot;i++){
        int x=e[i].fr,y=e[i].to;
        if(dep[x]<dep[y])swap(x,y);
        if(dis[x]==dis[y]+e[i].w)continue;
        d[++cnt]=(node){x,y,0,e[i].w+dis[x]+dis[y]};
    }
    sort(d+1,d+1+cnt,cmp);
    for(int i=1;i<=cnt;i++){
        int x=d[i].fr,y=d[i].to;
        x=getf(x),y=getf(y);
        while(x!=y){
            if(dep[x]<dep[y])swap(x,y);
            if(!ans[x])ans[x]=d[i].w-dis[x];
            x=f[x]=getf(fa[x]);
        }
    }
    for(int i=2;i<=n;i++){
        if(!ans[i])printf("-1
");
        else printf("%d
",ans[i]);
    }
    return 0;
}