P1144 最短路計數

題目描述

給出一個N個頂點M條邊的無向無權圖，頂點編號為1～N。問從頂點1開始，到其他每個點的最短路有幾條。

輸入輸出格式

輸入第一行包含2個正整數N，M，為圖的頂點數與邊數。

接下來M行，每行兩個正整數x, y，表示有一條頂點x連向頂點y的邊，請註意可能有自環與重邊。

輸出包括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%的數據，N<=1000000，M<=2000000。

迪傑斯特拉有毒啊，，，

卡了我好長時間。。。。

就是一個裸的最短路問題

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

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<queue>
  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<dian>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 }