首页 > 代码库 > P1144 最短路计数
P1144 最短路计数
P1144 最短路计数
题目描述
给出一个N个顶点M条边的无向无权图，顶点编号为1～N。问从顶点1开始，到其他每个点的最短路有几条。
输入输出格式
输入格式：
输入第一行包含2个正整数N，M，为图的顶点数与边数。
接下来M行，每行两个正整数x, y，表示有一条顶点x连向顶点y的边，请注意可能有自环与重边。
输出格式：
输出包括N行，每行一个非负整数，第i行输出从顶点1到顶点i有多少条不同的最短路，由于答案有可能会很大，你只需要输出mod 100003后的结果即可。如果无法到达顶点i则输出0。
输入输出样例
输入样例#1：
5 71 21 32 43 42 34 54 5
输出样例#1：
11124
说明
1到5的最短路有4条，分别为2条1-2-4-5和2条1-3-4-5（由于4-5的边有2条）。
对于20%的数据，N ≤ 100；
对于60%的数据，N ≤ 1000；
对于100%的数据，N<=1000000，M<=2000000。
分析：spfa，进行spfa时顺便数一下有几条最短路，每一次更新时，说明以前记录的都不是最短路，ans[] 更新成到达他的点的ans（乘法计数原理），相等时加上到他的点的ans（乘法计数原理）。注意要取模
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 using namespace std; 6 7 const int MAXN = 1000100; 8 const int mod = 100003; 9 struct Edge{10 int to,w,nxt;11 }e[MAXN<<1];12 int head[MAXN],dis[MAXN],ans[MAXN];13 bool vis[MAXN];14 int cnt,n,m;15 queue<int>q;16 17 void add(int u,int v,int w)18 {19 ++cnt;20 e[cnt].w = w;21 e[cnt].to = v;22 e[cnt].nxt = head[u];23 head[u] = cnt;24 }25 26 void spfa()27 {28 memset(dis,0x3f,sizeof(dis));29 q.push(1);30 dis[1] = 0;31 ans[1] = 1;32 vis[1] = true;33 while (!q.empty())34 {35 int u = q.front();36 q.pop();37 for (int i=head[u]; i; i=e[i].nxt)38 {39 int w = e[i].w;40 int v = e[i].to;41 if (dis[v] > dis[u]+w)42 {43 dis[v] = dis[u]+w;44 if (!vis[v])45 {46 q.push(v);47 vis[v] = true;48 }49 ans[v] = ans[u];50 }51 else if (dis[v] == dis[u]+w)52 ans[v] = (ans[v]+ans[u])%mod;53 }54 vis[u] = false;55 }56 }57 58 int main()59 {60 scanf("%d%d",&n,&m);61 for (int x,y,i=1; i<=m; ++i)62 {63 scanf("%d%d",&x,&y);64 add(x,y,1);65 add(y,x,1);66 }67 spfa(); 68 for (int i=1; i<=n; ++i)69 printf("%d\n",ans[i]);70 return 0;71 }
P1144 最短路计数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。