首页 > 其他 > 详细

『USACO』安全路经Travel (bzoj 1576)

时间:2018-09-26 00:47:04      阅读:51      评论:0      收藏:0      [点我收藏+]

标签:路径   using   原来   int   main   tmp   cmp   set   info   

题目链接

题目描述

技术分享图片



解题思路

没啥思路。

首先能想到要做一遍SPFA(堆优化),顺便记录一下每个点的最短路是由哪个边来的。

显然,1到所有的点的最短路组成了一棵树,但是接下来就不知道咋做了2333333。

我们发现:因为不能从原来的路径过来,所以我们要选择另一条路,也就将终点和另外的一个节点连接达到最短路,我们仔细想想,我们构造的最短路树已经满足了每个点到1号点的距离最近,所以从别的点转移过来一定能得到最近的距离。

先睡觉,明天再写qwq??



代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=100050;
const int maxm=200050;
int n,m,cnt=0,tot=0;
int head[maxm<<1],ne[maxm<<1],to[maxm<<1],v[maxm<<1],a[maxm],b[maxm],c[maxm];
bool flag[maxm<<1];
int dis[maxn],from[maxn],fa[maxn],num[maxn],ans[maxn];
bool vis[maxn];
struct nod{
    int x;
};
struct edge{
    int f,t,val;
};
edge e[maxm<<1];
inline bool operator < (nod a,nod b){
    return dis[a.x]>dis[b.x];
}
inline void add(int f,int t,int val){
    ne[++cnt]=head[f],head[f]=cnt,to[cnt]=t,v[cnt]=val;
}
inline void ini(){
    memset(ans,-1,sizeof(ans));
    for(register int i=0;i<maxn;i++)fa[i]=i;
}
inline int getfa(int x){
    return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
inline bool cmp(edge a,edge b){
    return a.val<b.val;
}
inline void spfa(){
    priority_queue<nod>q;
    memset(dis,0x3f,sizeof(dis));
    vis[1]=1,dis[1]=0;
    q.push((nod){1});
    while(!q.empty()){
        nod x=q.top();
        q.pop();
        vis[x.x]=0;
        for(register int i=head[x.x];i;i=ne[i]){
            if(dis[to[i]]>dis[x.x]+v[i]){
                dis[to[i]]=dis[x.x]+v[i];
                from[to[i]]=x.x;
                num[to[i]]=i;
                if(!vis[to[i]]){
                    vis[to[i]]=1;
                    q.push((nod){to[i]});
                }
            }
        }
    }
}
int main(){
    ini();
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=m;i++){
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
        add(a[i],b[i],c[i]),add(b[i],a[i],c[i]);
    }
    spfa();
    for(register int i=2;i<=n;i++){
        int tmp=num[i];
        if(num[i]&1)tmp++;
        else tmp--;
        flag[num[i]]=flag[tmp]=1;
    }
    for(register int i=1;i<=m;i++){
        if(flag[i<<1])continue;
        e[++tot]=(edge){a[i],b[i],dis[a[i]]+dis[b[i]]+c[i]};
    }
    sort(e+1,e+tot+1,cmp);
    for(register int i=1;i<=tot;i++){
        int f=e[i].f,t=e[i].t;
        f=getfa(f),t=getfa(t);
        while(f!=t){
            if(dis[f]<dis[t])swap(f,t);
            ans[f]=e[i].val-dis[f];
            fa[f]=from[f];
            f=getfa(f);
        }
    }
    for(register int i=2;i<=n;i++){
        printf("%d\n",ans[i]);
    }
}

『USACO』安全路经Travel (bzoj 1576)

标签:路径   using   原来   int   main   tmp   cmp   set   info   

原文:https://www.cnblogs.com/Fang-Hao/p/9704310.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号