信息学奥赛一本通T1499-最短路计数 堆优化+dijkstra

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
#define ll long long
const ll N=1e6+5;
const ll mod=1e5+3;
ll n,m;
struct node{
    ll id,dis;
    bool operator<(const node &x)const{
        return x.dis<dis;
    }
};
ll dis[N],js[N];
bool vis[N];
vector<node> a[N];
void dij(){
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;js[1]=1;
    priority_queue<node> q;
    q.push({1,0});
    while(!q.empty()){
        node x=q.top();q.pop();
        if(vis[x.id])continue;vis[x.id]=true;
        for(auto i:a[x.id]){
            ll v=i.id,w=i.dis;
            if(w+x.dis==dis[v])js[v]=(js[v]+js[x.id])%mod;
            if(w+dis[x.id]<dis[v]){
                dis[v]=w+dis[x.id];
                js[v]=js[x.id];
                q.push({v,dis[v]});
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(ll i=1;i<=m;i++){
        ll x,y;
        scanf("%lld%lld",&x,&y);
        a[x].push_back({y,1});
        a[y].push_back({x,1});
    }
    dij();
    for(ll i=1;i<=n;i++)printf("%lld\n",js[i]);
    return 0;
}