【题目描述】
给出一个 N 个顶点 M 条边的无向无权图,顶点编号为 1∼N。问从顶点 1 开始,到其他每个点的最短路有几条。
【输入】
给出一个 N 个顶点 M 条边的无向无权图,顶点编号为 1∼N。问从顶点 1 开始,到其他每个点的最短路有几条。
【输出】
输出 N 行,每行一个非负整数,第 i 行输出从顶点 1 到顶点 i 有多少条不同的最短路,由于答案有可能会很大,你只需要输出mod 100003后的结果即可。如果无法到达顶点 i 则输出 0。
【输入样例】
5 7 1 2 1 3 2 4 3 4 2 3 4 5 4 5
【输出样例】
1 1 1 2 4
【提示】
样例解释
1 到 5 的最短路有 4 条,分别为 2 条 1→2→4→5 和 2 条 1→3→4→5(由于 4→5 的边有 2 条)。
数据范围:
对于 20% 的数据,N≤100;
对于 60% 的数据,N≤1000;
对于 100% 的数据,1≤N≤100000,0≤M≤200000。
【代码】
登录CSDN复制 |
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<queue> using namespace std; inline int read() { char ch=getchar(); int x=0,f=1; while((ch>'9'||ch<'0')&&ch!='-') ch=getchar(); if(ch=='-') { f=-1; ch=getchar(); } while('0'<=ch&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } int mod=100003; int n,m,x,y,tot=0; const int N=1000005,M=4000005; int head[N],to[M],nxt[M],d[N],ans[N]; bool p[N]; priority_queue< pair< int,int > > q; void add(int x,int y) { to[++tot]=y; nxt[tot]=head[x]; head[x]=tot; } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { x=read();y=read(); add(x,y); add(y,x); } for(int i=1;i<=n;i++) { d[i]=1e9;p[i]=0; } d[1]=0;ans[1]=1; q.push(make_pair(0,1)); while(q.size()) { x=q.top().second; q.pop(); if(p[x]) continue; p[x]=1; for(int i=head[x];i;i=nxt[i]) { y=to[i]; if(d[y]>d[x]+1) { d[y]=d[x]+1; ans[y]=ans[x]; q.push(make_pair(-d[y],y)); } else if(d[y]==d[x]+1) { ans[y]+=ans[x]; ans[y]%=mod; } } } for(int i=1;i<=n;i++) printf("%d/n",ans[i]); return 0; } |
原创文章,作者:6024010,如若转载,请注明出处:https://blog.ytso.com/275125.html