小白刷题中
做一道BFS的题，参考https://www.acwing.com/video/3312/
题意
给定一条路径，小明沿着路径走。导航软件会给小明推荐最短路径。
首先，在点 s 处，导航软件会找到并显示出一条从点 s 到点 t 的最短路径。
如果小明的行进线路恰好与软件推荐线路一致，则软件推荐线路将不会发生任何改变。
但是，如果小明在某一点处，行进线路与软件推荐线路发生了分歧，例如，软件推荐前往点 v，小明却前往了点 w。
那么，在他到达点 w 后，软件就会实时更新推荐线路，即找到并显示出一条从点 w 到点 t 的最短路径。
导航软件会一直工作到小明到达点 t 为止，在这一过程中，软件的提供线路可能会经过若干次更新。
由于软件在推荐最短路径时具有随机性，所以在整个行进过程中，软件更新推荐线路的次数并不确定。
现在，给定有向图和行进路线，请你求出软件更新推荐线路的最小可能次数和最大可能次数。
输入输出
输入：第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 u,v，表示存在一条从点 u 到点 v 的有向边。
随后一行包含一个整数 k。
最后一行包含 k 个整数 p1,p2,…,pk。
输出：一行，空格隔开的两个整数，表示软件更新推荐路线的最小可能次数和最大可能次数。
思路
小明走的路径中，如果a->b不在一条最短路径中，那么最小可能次数和最大可能次数都要加一；
如果a->b在一条最短路径中，分情况讨论：1.a只能走b，导航就不需要更新；2.a还能走别的最短路径，那么最大推荐次数加一，最小推荐次数不变。
用bfs来更新给个点到给出路径终点的最短路径，以给出路径的终点作为bfs的起点，建立反向边，更新每个点的最短路径。同时还可以记录每个点有多少条出边。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int tot;
int head[N],ver[N],nxt[N]; //建邻接表需要的数组
int dist[N],cnt[N];
int path[N]; //路径
int q[N]; //队列
void add(int u, int v) // 添加一条边u->v
{
ver[++tot] = v;
nxt[tot] = head[u];
head[u] = tot;
}
void bfs(int start){ //计算每个点到终点的最短路径长度，同时记录下每个点在最短路上出边的数量
int hh=0, tt=0; //hh为遍历队列的指针，tt为队尾指针
memset(dist, 0x3f, sizeof dist); //初始化为无穷大
q[0] = start; //先将起点入队列
dist[start] = 0;
while(hh <= tt){
int u = q[hh++];
for(int i = head[u]; i;i = nxt[i]){ //遍历u的所有邻接点
int v = ver[i];
if(dist[v] > dist[u] + 1){
dist[v] = dist[u] + 1;
cnt[v]++;
q[++tt] = v;
}
else if(dist[v] == dist[u] + 1){
cnt[v]++;
}
}
}
}
int main()
{
int n,m,k;
cin >> n >> m;
for (int i = 0; i < m; i ++ ){
int u,v;
cin >> u >> v;
add(v,u); //建立反向边，因为要计算每个点到终点的最短路
}
cin >> k;
for (int i = 1; i <= k; i ++ ) cin >> path[i];
bfs(path[k]);
int minc=0,maxc=0;
for(int i = 1;i < k;i++){
int u=path[i],v=path[i+1]; //遍历给出路径上的点
if(dist[u] < dist[v] + 1){
minc++;maxc++;
}
else if(dist[u] == dist[v] + 1){
if(cnt[u] > 1) maxc++;
}
}
cout << minc << " " << maxc;
return 0;
}