【SPFA】洛谷 P1144 最短路计数

做了N遍的最短路计数。。。。。。。。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define N 2000007
#define mod 100003
struct node {
int to;
int nex;
}road[N<<1];
int vis[N], dis[N], frist[N], cnt = 0,ans[N];
queue<int> q;
void init() {
memset(frist, -1, sizeof(frist));
//	memset(dis, 1007, sizeof(dis));
memset(vis, 0, sizeof(vis));
memset(ans, 0, sizeof(ans));
}
void create(int u,int v) {
road[++cnt].nex = frist[u];
frist[u] =cnt;
road[cnt].to = v;
}
void SPFA(int x) {
q.push(x);
dis[x] = 1;//dis存这个节点的深度，当前深度为1
vis[x] = 1;
ans[x] = 1;//当前x到x的路径只有1条
while (!q.empty()) {
int now = q.front();
q.pop();
vis[now] = 0;//
//now 已取出，现要更新 to
for (int i = frist[now];i; i = road[i].nex)
{
int to = road[i].to;
if (dis[now] + 1 < dis[to])//若找到一条更短的路径
{
dis[to] = dis[now] + 1;
ans[to] = ans[now];//当前能到达此点的路径数也应相同
if (!vis[to])
vis[to]=1,q.push(to);
}
else if(dis[now]+1==dis[to]){//这种情况相当于有两条相同路径
ans[to] = (ans[now] + ans[to]) % mod;
}
else {
//此时的情况是从now到to不是最短路，则不走
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
init();
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
create(u, v);
create(v,u);
}
for (int i = 1; i <= n; i++)
dis[i]= 200007;//!注意要填一个最大值
SPFA(1);
for (int i = 1; i <= n; i++)
cout << ans[i]<<endl;
return 0;
}

最后

以上就是欣慰小猫咪为你收集整理的【SPFA】洛谷 P1144 最短路计数的全部内容，希望文章能够帮你解决【SPFA】洛谷 P1144 最短路计数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。