CodeForces 1321D. Navigation System（BFS）

传送门

题意

给一个图和一条路径，假设存在一个导航系统，它一开始会设定从起点到终点的最短路线，

如果沿着给定路径走偏离了导航系统设定的路线，那么它会在当前点重新设定最短路线

问导航系统最少和最多会重新设定路线多少次

题解

从终点开始，沿着反向边广搜，得到其余点到终点的最短路径距离和最短路线的数量

在给定路径中，如果当前点的最短距离 (le) 后一点的最短距离，那么后一点肯定不是系统设定的最短路线，此时最多最少都加 (1)

如果当前点小于后一点的距离，那么如果当前点可选择的点不止后一点，那么最多加 (1)

代码

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
using namespace std;
const int MAXN=2e5+10;
int n,m,dis[MAXN],a[MAXN],k,path[MAXN];
vector<int> g1[MAXN],g2[MAXN];
queue<int> que;

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;i++){
		scanf("%d%d",&u,&v);
		g1[u].push_back(v);
		g2[v].push_back(u);
	}
	scanf("%d",&k);
	for(int i=1;i<=k;i++) scanf("%d",&a[i]);
	memset(dis,0x3f,sizeof(dis));
	dis[a[k]]=0;que.push(a[k]);path[a[k]]=1;
	while(!que.empty()){
		int u=que.front();que.pop();
		for(int v:g2[u])
			if(dis[v]>dis[u]+1){
				dis[v]=dis[u]+1;
				path[v]=1;
				que.push(v);
			}
			else if(dis[v]==dis[u]+1) path[v]++;
	}
	int maxv=0,minv=0;
	for(int i=1;i<k;i++){
		if(dis[a[i]]<=dis[a[i+1]]) maxv++,minv++;
		else if(path[a[i]]>1) maxv++;
	}
	cout<<minv<<" "<<maxv<<endl;
	return 0;
}