AT_abc211_d [ABC211D] Number of Shortest paths 题解

zhuluoan / 2024-04-18 / 原文

题目简述

给定一张 $n$ 个点 $m$ 条边的无向无权图，问从 $1$ 到 $n$ 的最短路有多少条。

题目分析

设 $cnt_i$ 表示从 $1$ 到 $i$ 的最短路条数，$dis_i$ 表示最短路。

这道题可以考虑使用 BFS 做，对于一个点 $v$，设第一次更新它的点为 $u$，则它的转移应为 $cnt_v \leftarrow cnt_u$ 并且 $dis_v \leftarrow dis_u+1$，表示 $v$ 的最短路是由 $u$ 转移过来的。由于 BFS 的算法流程，此时 $v$ 的最短路已经被确定下来了，所以之后再有点 $x$ 更新 $v$ 时，仅当 $dis_v=dis_x+1$ 时，才有转移 $cnt_v \leftarrow cnt_v+cnt_x$，表示 $1 \rightarrow x \rightarrow v$ 是 $1 \rightarrow v$ 的另一条最短路。

最后输出 $cnt_n$ 即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define random(a,b) (rand()%(b-a+1)+a)
const int N=2e5+10,mod=1e9+7;
int n,m,x,y,dis[N],cnt[N],vis[N];
vector<int> G[N]; 
queue<int> q;
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    	cin>>x>>y;
    	G[x].push_back(y);
    	G[y].push_back(x);
	}
	memset(dis,0x3f,sizeof dis);
	dis[1]=0;
	cnt[1]=1;
	q.push(1);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=1;
		for(int v:G[u])
		{
			if(!vis[v])
			{
				dis[v]=dis[u]+1;
				cnt[v]+=cnt[u];
				q.push(v);
				vis[v]=1;
			}
			else if(dis[u]+1==dis[v])
			{
				cnt[v]=(cnt[v]+cnt[u])%mod;
			}
		}
	}
	cout<<cnt[n];
	return 0;
}