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;
}
```