点击查看代码
#include<bits/stdc++.h>
using namespace std;typedef pair<int,int> PII;
const int N=1e6+10,M=4e6+10;
int h[N],idx,e[M],ne[M];
int n,m;
int cnt[N];
int dist[N];
bool st[N];void add(int x,int y)
{e[idx]=x,ne[idx]=h[y],h[y]=idx++;
}void dijkstra()
{memset(dist,0x3f,sizeof dist);memset(st,0,sizeof st);dist[1]=0;priority_queue<PII,vector<PII>,greater<PII>> heap;heap.push({dist[1],1});cnt[1]=1;while(!heap.empty()){auto t=heap.top();int ver=t.second;heap.pop();if(st[ver]) continue;st[ver]=true;for(int i=h[ver];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[ver]+1){dist[j]=dist[ver]+1;heap.push({dist[j],j});cnt[j]=cnt[ver];}else if(dist[j]==dist[ver]+1){cnt[j]=(cnt[j]+cnt[ver])%100003;}}}
}int main()
{ios::sync_with_stdio(0),cin.tie(0);memset(h,-1,sizeof h);cin>>n>>m;for(int i=0;i<m;i++){int x,y;cin>>x>>y;add(x,y);add(y,x);}dijkstra();for(int i=1;i<=n;i++){cout<<cnt[i]<<endl;}return 0;}