题解 P2865 【[USACO06NOV]路障Roadblocks】

小手冰凉 · 2017-10-22 21:44:23 · 题解

大暴力做法

算两边SPFA（从1~n和从n~1各走一遍），然后计算次短路是枚举每条边，算出每条边1->该边的出发点+该边长度+该边结束点->n的值

（由于数组开小，贡献了N发WA）

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
const int M=400005;
int head[M],nxt[M],from[M],tail[M],e[M];
queue<int>q;
int dis[M],inq[M],dis2[M];
int t,n,m,ans,anst;
void addto(int x,int y,int z)
{
    nxt[++t]=head[x];
    from[t]=x;
    head[x]=t;
    tail[t]=y;
    e[t]=z;
}
void spfa(int s,int t,int *dis)
{
    memset(inq,0,sizeof(inq));
    q.push(s);
    dis[s]=0;
    inq[s]=1;
    while(!q.empty()){
        int k=q.front();
        q.pop();
        inq[k]=0;
        for(int i=head[k];i;i=nxt[i]){
            int x=tail[i];
            if(dis[x]>dis[k]+e[i]){
                dis[x]=dis[k]+e[i];
                if(!inq[x]){
                    q.push(x);
                    inq[x]=1;
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        addto(x,y,z);
        addto(y,x,z);
    }
    memset(dis,127/3,sizeof(dis));
    spfa(1,n,dis);
    anst=dis[n];
    ans=1e9;
    memset(dis2,127/3,sizeof(dis));
    spfa(n,1,dis2);
    for(int i=1;i<=t;i++)
        if(dis[from[i]]+dis2[tail[i]]+e[i]>anst)
            ans=min(dis[from[i]]+dis2[tail[i]]+e[i],ans);
    printf("%d",ans);
    return 0;
}