路障【SPFA】

本文主要是介绍路障【SPFA】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

求一个无向图的次短路。
$Input$

4 4
1 2 100
2 4 200
2 3 250
3 4 100

$Output$

450

---

思路：

这道题，正解是跑两遍$SPFA$，一遍是从点$1$，求出到达其他点的最短路径，记作$dis1[i]$；再从点$n$，也求出到达其他点的最短路径，记作$dis2[i]$；最后枚举每条边，若两个端点分别是$u[i]$和$v[i]$，长度为$dis[i]$，那么就是求次小的

$$dis[i]+dis1[u[i]]+dis2[v[i]]$$ 或 $$dis[i]+dis2[u[i]]+dis1[v[i]]$$

---

代码：

#include <cstdio>
#include <iostream>
#include <queue>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
using namespace std;const int Inf=99999999;
int n,m,x,y,z,t,dis1[30001],dis2[30001],vis[30001],head[30001],dis[300001],X[300001],Y[300001],ans,minn,sum;struct edge  //邻接表
{int next,to,dis;
}e[300001];void add(int from,int to,int d)  //连边
{t++;e[t].to=to;e[t].dis=d;e[t].next=head[from];head[from]=t;
}void spfa1()  //从点1开始跑SPFA
{queue<int> q;for (int i=1;i<=n;i++){vis[i]=0;dis1[i]=Inf;}vis[1]=1;dis1[1]=0;q.push(1);while (q.size())  //队列不为空{int u=q.front();vis[u]=0;q.pop();for (int i=head[u];i;i=e[i].next){int v=e[i].to;if (dis1[v]>dis1[u]+e[i].dis)  //更新最短路{dis1[v]=dis1[u]+e[i].dis;if (!vis[v]){q.push(v);vis[v]=1;}}}}
}void spfa2()  //从点n开始跑SPFA
{queue<int> q;for (int i=1;i<=n;i++){vis[i]=0;dis2[i]=Inf;}vis[n]=1;dis2[n]=0;q.push(n);while (q.size()){int u=q.front();vis[u]=0;q.pop();for (int i=head[u];i;i=e[i].next){int v=e[i].to;if (dis2[v]>dis2[u]+e[i].dis){dis2[v]=dis2[u]+e[i].dis;if (!vis[v]){q.push(v);vis[v]=1;}}}}
}int main()
{fre(block);scanf("%d%d",&n,&m);for (int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);dis[i]=z;X[i]=x;Y[i]=y;  //记录add(x,y,z);add(y,x,z);  //连边}spfa1();spfa2();minn=ans=Inf;for (int i=1;i<=m;i++)  //求次短路{sum=dis[i]+dis1[X[i]]+dis2[Y[i]];if (sum<minn){ans=minn;minn=sum;}else if (sum<ans&&sum!=minn) ans=sum;sum=dis[i]+dis2[X[i]]+dis1[Y[i]];if (sum<minn){ans=minn;minn=sum;}else if (sum<ans&&sum!=minn) ans=sum;}printf("%d\n",ans);return 0;
}

这篇关于路障【SPFA】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---