1025 - 最短路计数 - 统计最短路（？？？）

98 阅读 0 评论 65 点赞

我是靠谱客的博主开心老虎，这篇文章主要介绍1025 - 最短路计数 - 统计最短路（？？？），现在分享给大家，希望可以做个参考。

统计最短路

描述

给出n个点，m条带权无向边，问你从1号点到n号点的最短路中有多少种走法？

输入

第一行两个数n,m分别表示点的个数和边的个数。（2≤n≤5000，1≤m≤100000）接下来m行，每行3个数u,v,w表示u号点到v号点有一条距离为w的边。（1≤u,v≤n，0≤w≤5000）数据保证1号点能够到达n号点，点和边都可以被走多次。

输出

如果有无穷种走法，输出-1。否则输出走法的方案数mod 1000000009。

样例输入

4 4
1 2 1
1 3 1
2 4 1
3 4 1

样例输出

分析

这道题和上一道路径统计其实很相似，就只是多了一个无穷种走法（毒瘤啊……）
而仔细分析一下数据和题意，就会发现，其实无穷种走法，就是指在1~n的最短路中出现过0边权的边，这样他就可以反复地走来来回回地走这同一条边了
那我们需要做的就是判断在1~n的最短路径中是否出现过0边权的路
而判断一条边是否在最短路上，是不能够只简单地满足 $d i s [v] = = d i s [u] + w [e]$ 这个条件，因为这条边可能不存在在1~n这个最短路径上，只是在松弛的时候松弛到了这个地方
所以我们需要跑两遍最短路，正着跑一遍（从S出发），反着跑一遍（从T出发）最后判断这个条件： $d i s [S] [u] + w [e] + d i s [v] [T] = = d i s [S] [T]$ 即可

对了，想起一点，最短路计数的话最好就用dijkstra，用spfa的话，还有些细节要注意

代码

复制代码

#include<bits/stdc++.h>
#define in read()
#define P 1000000009
#define re register
#define N 5005
#define M 200009
#define ll long long
using namespace std;
inline int read(){
char ch;int f=1,res=0;
while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=-1;
while(ch>='0'&&ch<='9'){
res=(res<<3)+(res<<1)+ch-'0';
ch=getchar();
}
return f==1?res:-res;
}
int n,m;
bool vis[N];
int nxt[M],to[M],w[M],head[N],cnt=0;
int g[N][N],d[2][N],num[N];
ll ans[N];
void add(int x,int y,int z){nxt[++cnt]=head[x];head[x]=cnt;to[cnt]=y;w[cnt]=z;}
void dij(int S){
priority_queue<pair<int,int> > q;
int tp=(S==n)?1:0;
q.push(make_pair(0,S));d[tp][S]=0;ans[S]=1;
while(!q.empty()){
int u=q.top().second;
q.pop();if(vis[u]) continue;//vis
vis[u]=1;
for(int e=head[u];e;e=nxt[e]){
int v=to[e];
if(d[tp][v]==d[tp][u]+w[e]) ans[v]=(ans[v]+ans[u])%P;
else if(d[tp][v]>d[tp][u]+w[e]){
d[tp][v]=d[tp][u]+w[e];
ans[v]=ans[u];
q.push(make_pair(-d[tp][v],v));
}
}
}
}
int main(){
n=in;m=in;
int i,j,x,y,u,v,z;
for(i=1;i<=m;++i){
u=in;v=in;z=in;
add(u,v,z);add(v,u,z);
}
memset(d,127,sizeof(d));
dij(1);
memset(vis,0,sizeof(vis));memset(ans,0,sizeof(ans));
dij(n);
for(i=1;i<=n;++i)
{
for(int e=head[i];e;e=nxt[e])if(!w[e]){w[e]===0
j=to[e];
if(d[0][i]+d[1][j]==d[0][n]) return printf("-1"),0;
}
}
printf("%d",ans[1]);
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
#define in read()
#define P 1000000009
#define re register
#define N 5005
#define M 200009
#define ll long long
using namespace std;
inline int read(){
char ch;int f=1,res=0;
while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=-1;
while(ch>='0'&&ch<='9'){
res=(res<<3)+(res<<1)+ch-'0';
ch=getchar();
}
return f==1?res:-res;
}
int n,m;
bool vis[N];
int nxt[M],to[M],w[M],head[N],cnt=0;
int g[N][N],d[2][N],num[N];
ll ans[N];
void add(int x,int y,int z){nxt[++cnt]=head[x];head[x]=cnt;to[cnt]=y;w[cnt]=z;}
void dij(int S){
priority_queue<pair<int,int> > q;
int tp=(S==n)?1:0;
q.push(make_pair(0,S));d[tp][S]=0;ans[S]=1;
while(!q.empty()){
int u=q.top().second;
q.pop();if(vis[u]) continue;//vis
vis[u]=1;
for(int e=head[u];e;e=nxt[e]){
int v=to[e];
if(d[tp][v]==d[tp][u]+w[e]) ans[v]=(ans[v]+ans[u])%P;
else if(d[tp][v]>d[tp][u]+w[e]){
d[tp][v]=d[tp][u]+w[e];
ans[v]=ans[u];
q.push(make_pair(-d[tp][v],v));
}
}
}
}
int main(){
n=in;m=in;
int i,j,x,y,u,v,z;
for(i=1;i<=m;++i){
u=in;v=in;z=in;
add(u,v,z);add(v,u,z);
}
memset(d,127,sizeof(d));
dij(1);
memset(vis,0,sizeof(vis));memset(ans,0,sizeof(ans));
dij(n);
for(i=1;i<=n;++i)
{
for(int e=head[i];e;e=nxt[e])if(!w[e]){w[e]===0
j=to[e];
if(d[0][i]+d[1][j]==d[0][n]) return printf("-1"),0;
}
}
printf("%d",ans[1]);
return 0;
}