题目描述
给出一个N个顶点 M条边的无向无权图，顶点编号为 1∼N。问从顶点1开始，到其他每个点的最短路有几条。
题目限制
输入格式
第一行包含22个正整数 N,M，为图的顶点数与边数。
接下来M行，每行2个正整数 x,y，表示有一条由顶点x连向顶点y的边，请注意可能有自环与重边。
输出格式
共N行，每行一个非负整数，第i行输出从顶点1到顶点i有多少条不同的最短路，由于答案有可能会很大，你只需要输出 ans mod 100003后的结果即可。如果无法到达顶点i则输出0。
输入输出样例
解题思路
基于图论的DFS，我们可以通过记忆化搜索或者DP进行优化。我们这里选择使用DP。用SPFA预处理跑一边最短路
AC代码
#include #define inf 0x7FFFFFFFusing namespace std;#define Max 2000005#define mod 100003int n,m,head[Max],cnt,dis[Max],dp[Max];bool inq[Max],vis[Max];struct edge{int to,nxt;}e[Max];void SPFA();void DP();void add(int u,int v);int main(){cin>>n>>m;for(int i=1;i>a>>b;add(a,b),add(b,a);}SPFA();DP();for(int i=1;i<=n;++i) printf("%d\n",dp[i]);return 0;}void add(int u,int v){e[++cnt].to = v;e[cnt].nxt = head[u];head[u] = cnt;}void SPFA(){priority_queue <pair > q;for(int i=2 ;i dis[now] + 1){dis[to] = dis[now] + 1;q.push(make_pair(-dis[to],to));inq[to] = 1;}}}}void DP(){memset(vis,0,sizeof(vis));queue q;q.push(1);dp[1]=1;vis[1]=1;dis[1]=0;while(!q.empty()){int now = q.front();q.pop();for(int i=head[now];i;i=e[i].nxt){int to = e[i].to;if(dis[to] == dis[now] + 1){dp[to] += dp[now];dp[to] %= mod;if(!vis[to])q.push(to),vis[to] = 1;}}}}