Luogu P1144 最短路计数【最短路】 By cellur925

题目传送门

常规的最短路计数问题：注意有重边（重边不用理，看样例），自环（读入时过滤）。

另外这个无向图没有权，其实可以直接bfs做，但考虑到以后带权的情况，按spfa走了。

水题被卡了三次（嘤嘤嘤

第一次40pts：忘取膜了（？？？

第二次80pts：加了多余的判断，实质还是思路不清晰。

第三次100pts：去了冗余的判断，终于A了。

思路：

记录f数组表示f[i]为以i为终点，1为起点的最短路条数。初始只有f[1]=1。

其余在松弛的时候如果更新，f[v]=f[u]；

如果恰好相等（有相同最短路径）（这种情况不能和上面的情况一起判断），就f[v]+=f[u]

Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<queue>
 6 using namespace std;
 7 const int inf=2147483647;
 8 int n,m,s;
 9 int p=100003;
10 int num;
11 int pre[1000090],f[1000090];
12 struct node{
13     int to,val,next;
14 }edge[4000090];
15 int dis[1000090];
16 bool visit[1000090];
17 void add(int x,int y,int z)
18 {
19     num++;
20     edge[num].val=z;
21     edge[num].to=y;
22     edge[num].next=pre[x];
23     pre[x]=num;
24 }
25 void spfa()
26 {
27     queue<int>q;
28     for(int i=1;i<=n;i++)
29         dis[i]=inf;
30     q.push(1);
31     dis[1]=0;f[1]=1;
32     visit[1]=1;
33     while(!q.empty())
34     {
35         int u=q.front();
36         q.pop();
37         visit[u]=0;
38         for(int i=pre[u];i>0;i=edge[i].next)
39         {
40             int v=edge[i].to;
41             //if(u==1) (f[v]=1)%=p;
42             if(dis[v]>dis[u]+edge[i].val)
43             {
44                 dis[v]=dis[u]+edge[i].val;
45                 /*if(u!=1)*/ (f[v]=f[u])%=p;
46                 if(visit[v]==0)
47                 {
48                     visit[v]=1;
49                     q.push(v);
50                 }
51             }
52             else if(dis[v]==dis[u]+edge[i].val)
53                 (f[v]+=f[u])%=p;     
54         }
55     }
56 }
57 int main()
58 {
59     scanf("%d%d",&n,&m);
60     for(int i=1;i<=m;i++)
61     {
62         int x=0,y=0,z=0;
63         scanf("%d%d",&x,&y);
64         if(x==y) continue;
65         add(x,y,1);
66         add(y,x,1); 
67     }
68     spfa();
69     for(int i=1;i<=n;i++)
70         printf("%d
",f[i]);
71     return 0;
72 }

View Code

* Update 2018.9.22

做NOIp2017逛公园的时候发现自己的最短路计数算法有些Bug==

导致30分没有成功拿到。

做了一道加强版的最短路计数路径统计

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<queue>
 4 #include<cstring>
 5 
 6 using namespace std;
 7 typedef long long ll;
 8 
 9 int n,m,fake;
10 int vis[2090],dis[2090];
11 ll f[2090];
12 int e[2090][2090];
13 
14 void spfa()
15 {
16     memset(dis,63,sizeof(dis));
17     fake=dis[233];
18     queue<int>q;
19     q.push(1);vis[1]=1;dis[1]=0;f[1]=1;
20     while(!q.empty())
21     {
22         int u=q.front();q.pop();
23         vis[u]=0;
24         if(u==n) continue;
25         for(int i=1;i<=n;i++)
26         {
27             if(dis[i]==dis[u]+e[u][i])
28                 f[i]+=f[u];
29             if(dis[i]>dis[u]+e[u][i])
30             {
31                 dis[i]=dis[u]+e[u][i];
32                 f[i]=f[u];
33             }
34             if(f[i]&&!vis[i]) vis[i]=1,q.push(i);  
35         }
36         f[u]=0;
37     }
38 }
39 
40 int main()
41 {
42     scanf("%d%d",&n,&m);
43     memset(e,63,sizeof(e));
44     for(int i=1;i<=m;i++)
45     {
46         int x=0,y=0,z=0;
47         scanf("%d%d%d",&x,&y,&z);
48         e[x][y]=min(e[x][y],z);
49     }
50     spfa();
51     if(fake==dis[n]) printf("No answer");
52     else printf("%d %lld",dis[n],f[n]);
53     return 0;
54 }

View Code

还是用这个吧qwq

Luogu P1144 最短路计数 【最短路】 By cellur925

Luogu P1144 最短路计数【最短路】 By cellur925