我之前写的那个最短路标准模版就只是添加一个边就行

#include <bits/stdc++.h>
using namespace std;

const int N = 4000010,mod = 100003;
int n,m;
int d[N],st[N],res[N];
vector<int> e[N];
priority_queue<pair<int,int>> q;

void dijksrta(){
    memset(res,0,sizeof res);
    memset(d,0x3f,sizeof d);
    d[1]=0;
    res[1]=1;
    q.push({0,1});
    while(q.size()){
        auto t=q.top();
        q.pop();
        int u=t.second;
        if(st[u])   continue;
        st[u]=1;
        
        for(auto y:e[u]){
            if(d[y]>d[u]+1){
                d[y]=d[u]+1;
                res[y]=res[u];
                q.push({-d[y],y});
            }else if(d[y]==d[u]+1){
                res[y]+=res[u];
                res[y]%=mod;
            }
        }
    }
}
int main(){
    cin>>n>>m;
    int a,b;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        e[a].push_back(b);		//这里为啥是双向
        e[b].push_back(a);
    }
    dijksrta();
    for(int i=1;i<=n;i++)   cout<<res[i]<<endl;
    return 0;
}