dijstra算法

· · 题解

这道题很简单。

用最短路可以简单通过。

关于 SPFA，他死了。所以我们来用 Dijkstra 算法来解决这个问题。

我们可以简单的发现我们可以用拆限高杆后的最短距离减不拆限高杆的最短距离。

问题来了，我们怎么记录拆的限高杆呢？

其实，我们可以每拆一个限高杆后加 n。按照题目，最多可以拆两个限高杆。所以我们可以在建路时让有限高杆的路到路口编号加 n 的路口。再在加 n 的路上加上一个到路口编号加两个 n 的路口。最后，再做最短路。

让人激动的代码来了：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y;
    bool operator<(node l)const{
        return l.y<y;
    }
};
priority_queue<node>qi;
vector<node>vi[300005];
int n,m,a,b,c,d,di[30005];
bool vis[30005];
void dij(){
    memset(vis,false,sizeof(vis));
    memset(di,127,sizeof(di));
    di[1]=0;
    qi.push(node{1,0});
    while(!qi.empty()){
        int x=qi.top().x;
        qi.pop();
        if(vis[x]){
            continue;
        }
        for(int i=0;i<vi[x].size();i++){
            int a=vi[x][i].x,b=vi[x][i].y;
            if(di[a]>di[x]+b){
                di[a]=di[x]+b;
                qi.push(node{a,di[a]});
            }
        }
        vis[x]=true;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        if(d==0){
            vi[a].push_back(node{b,c});
            vi[b].push_back(node{a,c});
            vi[a+n].push_back(node{b+n,c});
            vi[b+n].push_back(node{a+n,c});
            vi[a+n+n].push_back(node{b+n+n,c});
            vi[b+n+n].push_back(node{a+n+n,c});
        }
        else{
            vi[a].push_back(node{b+n,c});
            vi[b].push_back(node{a+n,c});
            vi[a+n].push_back(node{b+n+n,c});
            vi[b+n].push_back(node{a+n+n,c});
        }
    }
    for(int i=1;i<=n;i++){
        vi[a].push_back(node{a+n,0});
        vi[a+n].push_back(node{a+n+n,0});
    }
    dij();
    if(di[n]-min(di[n*2],di[n*3])<0){
        cout<<0;
        return 0;
    }
    cout<<di[n]-min(di[n*2],di[n*3]);
}

感谢 Franz_Liszt 提供的 hack 数据，已改正。