最短路及最短路计数（SPFA）

54 阅读 0 评论 36 点赞

我是靠谱客的博主奋斗水蜜桃，最近开发中收集的这篇文章主要介绍最短路及最短路计数（SPFA），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define M 10005
#define INF 88888888
struct edge
{
int to,w;//保存边的信息，包括边的终点以及权值
};
long long dis[M];
//最短距离的估计值（当前该点的最短距离）
bool inq[M]; //标记该点是否在队列之中
vector<edge> g[M]; //利用一个vector保存，g[i]表示以i为起点的所有边的信息
int n,m,ee;
void spfa(int u)
{
for(int i = 0;i <= n;i++) //初始化
{
dis[i] = INF; //将估计值都初始化为INF
inq[i] = false; //初始化为不在队列中
}
dis[u] = 0; //起点的估计值直接就是0
inq[u] = true; //加入队列并进行标记
queue<int> q;
q.push(u);
while(!q.empty())
{
u = q.front();
inq[u] = false;
q.pop();
for(int i = 0;i < g[u].size();i++)
{
int v = g[u][i].to; //找出这条边对应的终点
int w = g[u][i].w;
//这条边对应的权值
if(dis[v] > dis[u]+w) //如果终点的最短距离比起点的最短距离加上这条边的权值大那么就更新
{
dis[v] = dis[u]+w;
if(!inq[v]) //如果v点的最短距离有所更新并且不在队列中，就将其加入队列。
{
//否则就不需要重复加入队列增加不必要的操作。
inq[v] = true;
//加入队列并标记
q.push(v);
}
}
}
}
}
int main()
{
while(scanf("%d %d %d",&n,&m,&ee)==3)
{
for(int i = 0;i <= n;i++) //清空vector避免多kase相互影响
g[i].clear();
for(int i = 0;i < m;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
edge e;
e.to = b;e.w = c;
g[a].push_back(e);
//e.to = a;
//g[b].push_back(e);
//题目中有说从a到b有这条路，并不是双向的。
}
spfa(ee);
for(int i = 1; i <= n; i++){
if(ee == i)
printf("0 ");
else{
if(dis[i] == 88888888) {
cout << 2147483647 << " ";
continue;
}
printf("%d ",dis[i]);
}
}
cout << endl;
}
return 0;
}

下面来一道例题：最短路计数

我们只需要将最短路的代码稍微改变一下

ans[1]初始化为1

更新边长的时候如果大于号就覆盖，相等的话（即有相同最短路径）就相加

对于无边权即使边权为1,

本题无需思考重边

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define M 4000000
#define INF 1e9
#define mod 100003
struct edge
{
int to,w;//保存边的信息，包括边的终点以及权值
};
long long dis[M];
//最短距离的估计值（当前该点的最短距离）
bool inq[M]; //标记该点是否在队列之中
vector<edge> g[M]; //利用一个vector保存，g[i]表示以i为起点的所有边的信息
int n,m,ee;
int ans[M];
void spfa(int u)
{
for(int i = 0;i <= n;i++) //初始化
{
dis[i] = INF; //将估计值都初始化为INF
inq[i] = false; //初始化为不在队列中
}
dis[u] = 0; //起点的估计值直接就是0
inq[u] = true; //加入队列并进行标记
queue<int> q;
q.push(u);
while(!q.empty())
{
u = q.front();
inq[u] = false;
q.pop();
for(int i = 0;i < g[u].size();i++)
{
int v = g[u][i].to; //找出这条边对应的终点
int w = g[u][i].w;
//这条边对应的权值
if(dis[v] > dis[u]+1) //如果终点的最短距离比起点的最短距离加上这条边的权值大那么就更新
{
dis[v] = dis[u]+1;
ans[v] = ans[u];
if(!inq[v]) //如果v点的最短距离有所更新并且不在队列中，就将其加入队列。
{
//否则就不需要重复加入队列增加不必要的操作。
inq[v] = true;
//加入队列并标记
q.push(v);
}
}
else if(dis[v] == dis[u] + 1){//计数操作
ans[v] += ans[u];
ans[v] %= mod;
}
}
}
}
int main()
{
ans[1] = 1;
scanf("%d %d",&n,&m);
for(int i = 0;i <= n;i++) //清空vector避免多kase相互影响
g[i].clear();
for(int i = 0;i < m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
edge e;
e.to = b;
e.w = 1;
g[a].push_back(e);
e.to = a;
g[b].push_back(e);
}
spfa(1);
for(int i = 1; i <= n; i++){
if(dis[i] == 1e9) {
cout << 0 << endl;
continue;
}
printf("%dn",ans[i]);
}
return 0;
}