P1144 最短路计数 spfa

P1144 最短路计数

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000010
const int inf = 0x7fffffff;
int n, m, x, y;
struct Edge{
int next;
int to;
}e[maxn];
int head[maxn],t=0;
void addEdge(int u,int v){
e[++t].to=v;
e[t].next=head[u];
head[u]=t;
}
int vis[maxn]={0},d[maxn],ans[maxn]={0};
void spfa(){
for(int i=1;i<=n;i++)
d[i]=inf;
queue< int > q;
d[1]=0;
vis[1]=1;
ans[1]=1;
q.push(1);
while(!q.empty()){
int s1=q.front();
q.pop();
int s2=head[s1];
while(s2){
if(d[e[s2].to]>d[s1]+1){
d[e[s2].to]=d[s1]+1;
ans[e[s2].to]=ans[s1];
if(!vis[e[s2].to]){
vis[e[s2].to]=1;
q.push(e[s2].to);
}
}
else if(d[e[s2].to]==d[s1]+1){
ans[e[s2].to]=(ans[s1]+ans[e[s2].to])%100003;
}
s2=e[s2].next;
}
}
}
int main(){
std::ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>x>>y;
addEdge(x,y);
addEdge(y,x);
}
spfa();
for(int i=1;i<=n;i++){
cout<<ans[i]<<endl;
}
return 0;
}

最后

以上就是健壮麦片为你收集整理的P1144 最短路计数 spfa的全部内容，希望文章能够帮你解决P1144 最短路计数 spfa所遇到的程序开发问题。

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