最短路的数量
2025-01-24 20:18:38
发布于：上海
4阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> tr[200010];
long long dist[200010];
long long dp[200010];
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
tr[x].push_back(y);
tr[y].push_back(x);
}
for(int i=1;i<=n;i++)dist[i]=0x3f3f3f3f;
//memset(dist,0x3f,sizeof(dist));
long long mod = 1e9+7;
queue<int> q;
q.push(1);
dist[1]=0;
dp[1] =1;
while(q.size()){
int u = q.front();
//cout<<u<<endl;
q.pop();
for(int x:tr[u]){
if(dist[x] > dist[u]+1){
dp[x] = dp[u];
dist[x] = dist[u]+1;
q.push(x);
}else if(dist[x]==dist[u]+1){
dp[x] = dp[x] + dp[u];
dp[x]%=mod;
}
}
}
if(dist[n]==0x3f3f3f3f)cout<<0;
else cout<<dp[n];
return 0;
}
这里空空如也
有帮助，赞一个