题解 P2865 【[USACO06NOV]路障Roadblocks】

· · 题解

A了之后，特地看了眼八篇题解，发现我和大佬的思路都不一样蒟蒻的我瑟瑟发抖，特此写篇题解向大佬们请教

我的思路来源于P1186玛丽卡

我们可以在计算最短路时（我是dij党，能不用SPFA就不用，虽然这题的标签是SPFA），记录这个最短路需要哪几条路

然后不断把这些路中的一个去掉，计算最短路，取最小值

想到这里，我们就可以拿到90分了

看似完美无缺的思路为毛不能A？This is a question.

因为我们没有考虑如果一条边都不删会怎样（惊讶脸）

没有删是怎么回事？？？

这是因为题目中说，一条边可以走多次，那么我们可以沿着那个一开始的最短路来回走，即一开始的最短路*3，这个数可能比我们后来算的那个数小

那么现在正确答案就是这两个数中较小的那一个

贴上AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define M(x,y) make_pair(x,y)
using namespace std;
int head[5010],nex[200010],to[200010],v[200010],tl;
int dis[5010],n,m,f[5010],fr[200010];
bool vis[5010],b[200010];
priority_queue< pair<int,int> > q;
inline void add(int x,int y,int z){
    to[++tl]=y;v[tl]=z;nex[tl]=head[x];head[x]=tl;fr[tl]=x;
    to[++tl]=x;v[tl]=z;nex[tl]=head[y];head[y]=tl;fr[tl]=y;
}
inline int read(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=m;i++){
        int x=read(),y=read(),z=read();
        add(x,y,z);
    }
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    q.push(M(0,1));
    while(q.size()){
        int x=q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x]=true;
        for(int i=head[x];i;i=nex[i]){
            int y=to[i],l=v[i];
            if(dis[y]>dis[x]+l){
                dis[y]=dis[x]+l;
                f[y]=i;
                q.push(M(-dis[y],y));
            }
        }
    }
    int To=n,Fr=fr[f[n]],ans=0x7f7f7f7f,mi=dis[n]*3;
    while(To!=1){
        b[f[To]]=true;
        for(int i=2;i<=n;i++) dis[i]=0x3f3f3f3f;
        for(int i=1;i<=n;i++) vis[i]=false;
        q.push(M(0,1));
        while(q.size()){
            int x=q.top().second;
            q.pop();
            if(vis[x]) continue;
            vis[x]=true;
            for(int i=head[x];i;i=nex[i]){
                if(b[i]) continue;
                if(dis[to[i]]>dis[x]+v[i]){
                    dis[to[i]]=dis[x]+v[i];
                    q.push(M(-dis[to[i]],to[i]));
                }
            }
        }
        b[f[To]]=false;
        ans=min(ans,dis[n]);
        To=Fr;Fr=fr[f[To]];
    }
    printf("%d",min(ans,mi));
    return 0;
}