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;
}