spfa次短路

钱逸凡 · 2018-09-18 20:08:38 · 题解

看到题解里好多dijkstra的，我就来一篇spfa的吧

好像有很多题解说spfa要跑两遍？

但是我只用了一遍就A了啊

思路：

dist数组开二维，分别装最小距离和次小距离。

先像往常一样打一个spfa，然后往里面塞一些if就好了。

更新最小距离的条件不用说了，

更新次小距离的条件有三种：

1.更新了最小距离，要把上次的最小距离先拿给次小距离（刚开始没想到这个条件，调了好久），因为上次的最小距离就是比当前距离大且最小的距离（即为次短距离）。

2.虽然可能当前路径无法更新最小距离，但可能更新次小距离，要加判断

3.从上一个点的次短距离更新这一个点的次短距离

注意：

想转移次短距离，必须保证该距离小于最短距离。

完整代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
inline int Read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
int n,m;
int dist[10101][2];//dist[i][0]装最短路,dist[i][1]次短路
struct Node{
    int v;
    int next;
    int val;
}node[202020];
int head[5050],top;
inline void addedge(int u,int v,int val){
    node[++top].v=v;
    node[top].val=val;
    node[top].next=head[u];
    head[u]=top;
}
inline void add(int u,int v,int val){
    addedge(u,v,val);
    addedge(v,u,val);
}
int inque[5050];
void spfa(){
    int s=1;
    memset(dist,0x3f,sizeof(dist));
    queue<int>q;
    q.push(s);
    dist[s][0]=0;
    dist[s][1]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inque[u]=0;
        for(int i=head[u];i;i=node[i].next){
            int d=node[i].v;
            if(dist[d][0]>dist[u][0]+node[i].val){
                dist[d][1]=dist[d][0];//条件1 
                dist[d][0]=dist[u][0]+node[i].val;
                if(inque[d]==0){
                    q.push(d);
                    inque[d]=1;
                }
            }
            if(
            (dist[d][1]>dist[u][0]+node[i].val&&dist[u][0]+node[i].val>dist[d][0])
            ||(dist[d][1]==dist[d][0])){//从最短路转移（条件2） 
                dist[d][1]=dist[u][0]+node[i].val;
                if(inque[d]==0){
                    q.push(d);
                    inque[d]=1;
                }
            }
            if(dist[d][1]>dist[u][1]+node[i].val&&dist[u][1]+node[i].val>dist[d][0]){//从次短路转移（条件3） 
                dist[d][1]=dist[u][1]+node[i].val;
                if(inque[d]==0){
                    q.push(d);
                    inque[d]=1;
                }
            }
        }
    }
}
int main(){
    register int i;
    int u,v,val;
    n=Read(),m=Read();
    for(i=1;i<=m;i++){
    u=Read(),v=Read(),val=Read();
    add(u,v,val);
    }
    spfa();
    printf("%d",dist[n][1]);
    return 0;
}