题目描述
给出一张n个节点m条边的无向连通图，求这张图的最短路数量。
思路
我们可以直接进行DIjkstra，在进行最短路算法时，如果dis[u]由dis[v]转移过来，那么根据加法原理，到u的最短路数量ans[u]=ans[v]，而对于相等最短路，加上可以转移过来的ans[v]即可。
代码
#include <bits/stdc++.h> using namespace std; const int N=1e5+10,M=2e5+10,mod=100003; int head[N],nxt[M<<1],to[M<<1],tot; int dis[N],ans[N]; bool vis[N]; void add_edge(int x,int y) { nxt[++tot]=head[x]; head[x]=tot; to[tot]=y; } void Dijkstra() { memset(dis,0x3f,sizeof(dis)); priority_queue<pair<int,int> >q; dis[1]=0;ans[1]=1;q.push(make_pair(0,1)); while(!q.empty()) { int u=q.top().second;q.pop(); if(vis[u])continue ; vis[u]=1; for(int i=head[u];i;i=nxt[i]) { int v=to[i]; if(dis[v]>dis[u]+1) { dis[v]=dis[u]+1; ans[v]=ans[u]%mod; q.push(make_pair(-dis[v],v)); } else if(dis[v]==dis[u]+1) ans[v]=(ans[v]+ans[u])%mod; } } } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); add_edge(x,y);add_edge(y,x); } Dijkstra(); for(int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0; }