题目描述
给出一个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。
分析：spfa，进行spfa时顺便数一下有几条最短路，每一次更新时，说明以前记录的都不是最短路，ans[] 更新成到达他的点的ans，相等时加上到他的点的ans。注意要取模
//Gang
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#define FOR(x,y,z) for(int x=y;x<=z;x++)
#define REP(x,y,z) for(int x=y;x>=z;x--)
#define ll long long
using namespace std;
;
int n,m;
int x,y;
];
];
];
];
int cnt;
struct node{
int v,next,dis;
}e[];
void add(int u,int v,int dis)
{
cnt++;
e[cnt].next=hd[u];
e[cnt].v=v;
e[cnt].dis=dis;
hd[u]=cnt;
}
void SPFA()
{
memset(dis,0x3f,sizeof(dis));
queue<int>q;
q.push();
book[]=;
dis[]=;
ans[]=;
while(!q.empty())
{
int u=q.front();
q.pop();
book[u]=;
for(int i=hd[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]>dis[u]+e[i].dis)
{
dis[v]=dis[u]+e[i].dis;
if(!book[v])
{
q.push(v);
book[v]=;
}
ans[v]=ans[u];
}
else if(dis[v]==dis[u]+e[i].dis)
{
ans[v]+=ans[u];
ans[v]%=mod;
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
FOR(i,,m)
{
scanf("%d%d",&x,&y);
add(x,y,);
add(y,x,);
}
SPFA();
FOR(i,,n)
printf("%d\n",ans[i]);
;
}