题目描述
给出一个N个顶点M条边的无向无权图,顶点编号为1~N。问从顶点1开始,到其他每个点的最短路有几条。
输入输出格式
输入格式:
输入第一行包含2个正整数N,M,为图的顶点数与边数。接下来M行,每行两个正整数x, y,表示有一条顶点x连向顶点y的边,请注意可能有自环与重边。
输出格式:
输出包括N行,每行一个非负整数,第i行输出从顶点1到顶点i有多少条不同的最短路,由于答案有可能会很大,你只需要输出mod 100003后的结果即可。如果无法到达顶点i则输出0。输入输出样例
输入样例#1: 复制
5 7 1 2 1 3 2 4 3 4 2 3 4 5 4 5 输出样例#1: 复制 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%的数据,N<=1000000,M<=2000000。
最短路,仅仅加了一个判断是否同为最短路。
#includeusing namespace std;const int maxn=2000000+5;int n,m,head[maxn],cnt,q[maxn*2+5],dis[maxn];int ans[maxn];bool vis[maxn];struct Edge{ int next,to;}edge[maxn*2];inline void add(int bg,int ed){ edge[++cnt].to=ed; edge[cnt].next=head[bg]; head[bg]=cnt;}inline void spfa(){ ans[1]=1; dis[1]=0; vis[1]=1; q[1]=1; int h=0,t=1; while(h dis[u]+1){ dis[edge[i].to]=dis[u]+1; ans[edge[i].to]=ans[u]; if(!vis[edge[i].to]){ vis[edge[i].to]=1; q[++t]=edge[i].to; } } else if(dis[edge[i].to]==dis[u]+1){ ans[edge[i].to]+=ans[u]; ans[edge[i].to]%=100003; } } }}int main(){ memset(dis,0x3f,sizeof dis); scanf("%d%d",&n,&m); for(register int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); }spfa(); for(register int i=1;i<=n;i++){ printf("%d\n",ans[i]); } return 0;}