题目描述

#include<bits/stdc++.h>
#include<queue>
using namespace std;
const int N= 1e5+1,M=4e5+1;
int h[M],ne[M],e[M],w[M],idx;
int vis[N],d[N],cnt[N],mod = 100003;
int n,m;

void add(int a,int b,int c){
    w[idx] = c;
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void spfa(){
    memset(d,0x3f,sizeof d);
    queue<int> q;
    q.push(1);
    d[1] = 0;
    vis[1] = 1;
    cnt[1] = 1;
    while(q.size()){
        int t = q.front();
        vis[t] = 0; 
        for(int i=h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(d[j] > d[t] + w[i]){
                d[j] = d[t] + w[i];
                if(!vis[j]){
                    q.push(j);
                    vis[j] = 1;
                    cnt[j] = cnt[t];
                }
            }else if(d[j]==d[t]+w[i]){
                cnt[j]+=cnt[t];
                cnt[j] %= mod;
            }
        }
        q.pop();
    }
}

int main(){
    cin >> n >> m;
    memset(h,-1,sizeof h);
    while(m--){
        int u,v;
        cin >> u >> v;
        add(u,v,1);
        add(v,u,1); 
    }
    spfa();
    for(int i=1; i <= n; i++){
        cout << cnt[i] << endl;
    }
    return 0;
}