题目描述

给出一个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。

 

迪杰斯特拉有毒啊，，，

卡了我好长时间。。。。

就是一个裸的最短路问题

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

1 #include
        
           2 #include
         
            3 #include
          
             4 #include
           
              5 #include
            
               6 using namespace std;  7 void read(int & n)  8 {  9     char c='+';int x=0;     10     while(c<'0'||c>'9')c=getchar(); 11     while(c>='0'&&c<='9') 12     { 13         x=x*10+c-48; 14         c=getchar(); 15     } 16     n=x; 17 } 18 const int MAXN=1000401; 19 const int maxn=0x7fffff; 20 int tot[MAXN]; 21 struct node 22 { 23     int u,v,w,nxt; 24 }edge[MAXN*4]; 25 int head[MAXN]; 26 int num=1; 27 int n,m; 28 int dis[MAXN]; 29 int vis[MAXN]; 30 struct dian 31 { 32     int bh; 33     int jl; 34 }a[MAXN]; 35 void add(int x,int y) 36 { 37     edge[num].u=x; 38     edge[num].v=y; 39     edge[num].w=1; 40     edge[num].nxt=head[x]; 41     head[x]=num++; 42 } 43 bool operator <(dian a,dian b){
      return a.jl>b.jl;} 44 void dj() 45 { 46      47     priority_queue
             
              q; 48 dis[1]=0; 49 vis[1]=1; 50 tot[1]=1; 51 dian now; 52 now.bh=1; 53 now.jl=0; 54 q.push(now); 55 while(q.size()!=0) 56 { 57 dian p=q.top(); 58 q.pop(); 59 vis[p.bh]=0; 60 if(dis[p.bh]!=p.jl)continue; 61 for(int i=head[p.bh];i!=-1;i=edge[i].nxt) 62 { 63 int will=edge[i].v; 64 if(dis[will]==dis[p.bh]+edge[i].w) 65 { 66 tot[will]=(tot[p.bh]+tot[will])%100003; 67 } 68 if(dis[will]>dis[p.bh]+edge[i].w) 69 { 70 dis[will]=dis[p.bh]+edge[i].w; 71 tot[will]=(tot[p.bh])%100003; 72 if(vis[will]==0) 73 { 74 dian nxt; 75 nxt.bh=will; 76 nxt.jl=dis[will]; 77 q.push(nxt); 78 vis[will]=1; 79 } 80 } 81 } 82 } 83 84 } 85 int main() 86 { 87 read(n);read(m); 88 for(int i=1;i<=n;i++) 89 dis[i]=maxn,head[i]=-1; 90 for(int i=1;i<=m;i++) 91 { 92 int x,y; 93 read(x);read(y); 94 add(x,y);add(y,x); 95 } 96 dj(); 97 for(int i=1;i<=n;i++) 98 printf("%d\n",tot[i]); 99 return 0;100 }