题解 P2934 【[USACO09JAN]安全出行Safe Travel】

iostream · 2017-09-28 22:15:53 · 题解

这题可以用最短路算法做，求出单源最短路之后，形成一颗最短路树。

我们发现从点u走到点v，显然必须要通过不在树上的边，这样我们只要求min{w(u,v)+d(u)+d(v)-d(f)}

枚举点f，统计答案时再用并查集维护u,v是否联通即可。

注意：这里必须用堆优化Dijkstra跑最短路，spfa要TLE

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int N=200010;
int n,m,adj[N<<1],nxt[N<<1],head[N],tot,w[N<<1];
int vis[N],dis[N],fa[N];
inline void adde(int u,int v,int d){
    adj[++tot] = v;
    w[tot] = d;
    nxt[tot] = head[u];
    head[u] = tot;
}
inline void spfa(int start){
    queue<int> q;
    q.push(start);
    memset(dis,127,sizeof(dis));
    memset(vis, 0 ,sizeof(vis));
    vis[start]=1;dis[start]=0;
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int e=head[u],v;e;e=nxt[e]){
            v=adj[e];
            if(dis[u]+w[e]<dis[v]){
                dis[v]=dis[u]+w[e];
                fa[v]=u;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
void SPFA(int S)
{
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    for (int i=1; i<=n; i++) dis[i]=1<<30;
    q.push(make_pair(0,S)); dis[S]=0;
    while (!q.empty())
        {
            int now=q.top().second;
            int Dis=q.top().first;
            q.pop();
            if (Dis>dis[now]) continue;
            for (int i=head[now]; i; i=nxt[i])
                if (Dis + w[i] < dis[adj[i]])
                    dis[adj[i]]=Dis+w[i],
                    fa[adj[i]]=now,
                    q.push(make_pair(dis[adj[i]],adj[i]));
        }
}
struct road{
    int u,v,w;
}a[N];
int cnt;
inline bool cmp(road a,road b){
    return a.w<b.w;
}
int f[N],ans[N],num;
inline int find(int i){return f[i]==i?i:f[i]=find(f[i]);} 
inline void calc(road x){
    int u=x.u,v=x.v,t=x.w;
    while(find(u)!=find(v)){ num++;
        if(dis[find(u)]<dis[find(v)])swap(u,v);
        ans[find(u)]=min(ans[find(u)],t-dis[find(u)]);
        u=f[find(u)]=fa[find(u)];
    }
}
inline int get(){
    char c; int s;
    for(c=getchar();c<'0'||c>'9';c=getchar());
    for(s=0;c>='0'&&c<='9';c=getchar())s=(s<<1)+(s<<3)+c-'0';
    return s;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v,l;i<=m;i++){
        u=get(),v=get(),l=get();
        adde(u,v,l);adde(v,u,l);
    }
    //spfa(1);
    SPFA(1);
    for(int i=2;i<=tot;i+=2){
        int u=adj[i],v=adj[i-1];
        if(u!=fa[v]&&v!=fa[u]){
            a[++cnt].u=u,a[cnt].v=v,a[cnt].w=w[i]+dis[u]+dis[v];
        }
    }
    sort(a+1,a+1+cnt,cmp);
    for(int i=1;i<=n;i++)f[i]=i,ans[i]=1<<30;
    for(int i=1;i<=cnt&&num<n-1;i++)
        calc(a[i]);
    for(int i=2;i<=n;i++)
        printf("%d\n",ans[i]==1<<30?-1:ans[i]);
    return 0;
}