题目描述

给出一个N(1e6)个顶点M(2e6)条边的无向无权图，顶点编号为1−N。问从顶点1开始，到其他每个点的最短路有几条。

__________________________

dij求出每个点的最短路，如果最短路更新，则F[V]=F[U],如果刚好等于最短路，则f[v]+=f[u]，最终输出答案。记得取模！

__________________________

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e6+10;
 4 const int maxm=4e6+10;
 5 struct edge
 6 {
 7     int u,v,w,nxt;
 8 }e[maxm];
 9 int head[maxn],js;
10 void addage(int u,int v,int w)
11 {
12     e[++js].u=u;e[js].v=v;e[js].w=w;
13     e[js].nxt=head[u];head[u]=js;
14 }
15 int dis[maxn],f[maxn];
16 bool vis[maxn];
17 int n,m;
18 struct node
19 {
20     int dis,no;
21     bool operator < (const node &a)const
22     {
23         return dis>a.dis;
24     }
25 };
26 priority_queue<node>q;
27 void dij()
28 {
29     memset(dis,0x3f,sizeof dis);
30     dis[1]=0;f[1]=1;
31     q.push((node){0,1});
32     while(!q.empty())
33     {
34         node uu=q.top();q.pop();
35         int u=uu.no,d=uu.dis;
36         if(vis[u])continue;
37         vis[u]=1;
38         for(int i=head[u];i;i=e[i].nxt)
39         {
40             int v=e[i].v;
41             if(vis[v])continue;
42             if(dis[v]>dis[u]+e[i].w)
43             {
44                 dis[v]=dis[u]+e[i].w;
45                 f[v]=f[u];
46                 q.push((node){dis[v],v});
47             }
48             else if(dis[v]==dis[u]+e[i].w)
49             {
50                 f[v]=(f[u]+f[v])%100003;
51             }
52         }
53     }
54 }
55 int main()
56 {
57     scanf("%d%d",&n,&m);
58     for(int u,v,i=1;i<=m;++i)
59     {
60         scanf("%d%d",&u,&v);
61         addage(u,v,1);addage(v,u,1);
62     }
63     dij();
64     for(int i=1;i<=n;++i)printf("%d\n",f[i]);
65     return 0;
66 }