bfs

从终点 t 开始进行 BFS到起点 t，在 BFS 结束后，统计 s 到 t 的路径。具体做法是，对于所有经过两个连续路径节点 a 和 b 的路径，统计路径数 minc 和 maxc，其中 minc 表示这样的路径中最少的需要修改的路径数，maxc 表示这样的路径中最多需要修改的次数。特别地，当 a 向 b 有直接连边时，如果 a 节点和 b 节点之间的距离 dist[a] < dist[b] + 1，那么从 a 到 b 的路径上不会有其他点，所以这样的路径也属于 minc 类型的路径。

从终点开始 BFS 的目的是为了在搜索过程中记录每个节点到终点的距离和路径经过其它点的数量。这样可以方便地对任意两个路径节点之间的路径类型进行分类和统计。如果从起点开始 BFS，那么需要考虑所有的路径才能确认某个路径是否满足题目中所给定的条件。这样做的时间复杂度会很高，代码量也变大。从终点开始 BFS 可以简化路径类型的分类和计数。因为每个节点在 BFS 中被处理的次数不会超过它的出度，这样可以避免死循环和重复计算，同时也可以减少运行时间和空间开销。此外，从终点开始 BFS 还可以保证每个节点在 BFS 中被更新的距离值和路径数量都是最终值，无需再次更新。

#include <bits/stdc++.h>

using namespace std;

const int N = 200010;

int n, m;
int h[N], e[N], ne[N], idx;
int dist[N], cnt[N], q[N];//cnt路径数
int path[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs(int start)
{
    memset(dist, 0x3f, sizeof dist);
    int hh = 0, tt = -1;
    dist[start] = 0;
    q[ ++ tt] = start;

    while (hh <= tt) 
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i]) 
        {
            int j = e[i];
            if (dist[j] > dist[t] + 1) 
            {
                dist[j] = dist[t] + 1;
                cnt[j] = 1;//只有一条路径
                q[ ++ tt] = j;
            }
            else if (dist[j] == dist[t] + 1) 
                cnt[j] ++ ;//路径数量加1 
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(b, a); //加反向边，因为要反向bfs
    }

    int k;
    scanf("%d", &k);
    for (int i = 1; i <= k; i ++ ) scanf("%d", &path[i]);
    bfs(path[k]);

    int minc = 0, maxc = 0;
    for (int i = 1; i < k; i ++ ) 
    {
        int a = path[i], b = path[i + 1];
        if (dist[a] < dist[b] + 1)//说明从b点到a点走的不是最短路,需要重新规划路线
            minc ++ , maxc ++ ;
        else if (cnt[a] > 1) maxc ++ ; 
    }

    printf("%d %d\n", minc, maxc);
    return 0;
}