D. Navigation System

Link：D. Navigation System

Description

The map of Bertown can be represented as a set of n intersections, numbered from 1 to n and connected by m one-way roads. It is possible to move along the roads from any intersection to any other intersection. The length of some path from one intersection to another is the number of roads that one has to traverse along the path. The shortest path from one intersection v to another intersection u is the path that starts in v, ends in u and has the minimum length among all such paths.

Polycarp lives near the intersection s and works in a building near the intersection t. Every day he gets from s to t by car. Today he has chosen the following path to his workplace: $p_1$, $p_2$, ..., $p_k$, where $p_1 = s$, $p_k = t$, and all other elements of this sequence are the intermediate intersections, listed in the order Polycarp arrived at them. Polycarp never arrived at the same intersection twice, so all elements of this sequence are pairwise distinct. Note that you know Polycarp's path beforehand (it is fixed), and it is not necessarily one of the shortest paths from s to t.

Polycarp's car has a complex navigation system installed in it. Let's describe how it works. When Polycarp starts his journey at the intersection s, the system chooses some shortest path from s to t and shows it to Polycarp. Let's denote the next intersection in the chosen path as v. If Polycarp chooses to drive along the road from s to v, then the navigator shows him the same shortest path (obviously, starting from v as soon as he arrives at this intersection). However, if Polycarp chooses to drive to another intersection w instead, the navigator rebuilds the path: as soon as Polycarp arrives at w, the navigation system chooses some shortest path from w to t and shows it to Polycarp. The same process continues until Polycarp arrives at t: if Polycarp moves along the road recommended by the system, it maintains the shortest path it has already built; but if Polycarp chooses some other path, the system rebuilds the path by the same rules.

Here is an example. Suppose the map of Bertown looks as follows, and Polycarp drives along the path [1, 2, 3, 4] (s=1, t=4):

1. When Polycarp starts at 1, the system chooses some shortest path from 1 to 4. There is only one such path, it is [1,5,4];
2. Polycarp chooses to drive to 2, which is not along the path chosen by the system. When Polycarp arrives at 2, the navigator rebuilds the path by choosing some shortest path from 2 to 4, for example, [2,6,4] (note that it could choose [2,3,4]);
3. Polycarp chooses to drive to 3, which is not along the path chosen by the system. When Polycarp arrives at 3, the navigator rebuilds the path by choosing the only shortest path from 3 to 4, which is [3,4];
4. Polycarp arrives at 4 along the road chosen by the navigator, so the system does not have to rebuild anything.

Overall, we get 2 rebuilds in this scenario. Note that if the system chose [2,3,4] instead of [2,6,4] during the second step, there would be only 1 rebuild (since Polycarp goes along the path, so the system maintains the path [3,4] during the third step).

The example shows us that the number of rebuilds can differ even if the map of Bertown and the path chosen by Polycarp stays the same. Given this information (the map and Polycarp's path), can you determine the minimum and the maximum number of rebuilds that could have happened during the journey?

Input
The first line contains two integers n and m ($2 \le n \le m \le 2 \cdot 10^5$) — the number of intersections and one-way roads in Bertown, respectively.
Then m lines follow, each describing a road. Each line contains two integers u and v $(1 \leq u, v \leq n, u \neq v)$
denoting a road from intersection u to intersection v. All roads in Bertown are pairwise distinct, which means that each ordered pair (u,v) appears at most once in these m lines (but if there is a road (u,v), the road (v,u) can also appear).

The following line contains one integer k ($2 \le k \le n$) — the number of intersections in Polycarp's path from home to his workplace.

The last line contains k integers $p_1$, $p_2$, ..., $p_k$($1 \le p_i \le n$, all these integers are pairwise distinct) — the intersections along Polycarp's path in the order he arrived at them. p1 is the intersection where Polycarp lives ($s = p_1$), and pk is the intersection where Polycarp's workplace is situated ($t = p_k$). It is guaranteed that for every $i \in [1, k - 1]$ the road from $p_i$ to $p_{i + 1}$ exists, so the path goes along the roads of Bertown.

Output
Print two integers: the minimum and the maximum number of rebuilds that could have happened during the journey.

Examples
input
6 9
1 5
5 4
1 2
2 3
3 4
4 1
2 6
6 4
4 2
4
1 2 3 4
output
1 2
input
7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1
7
1 2 3 4 5 6 7
output
0 0
input
8 13
8 7
8 6
7 5
7 4
6 5
6 4
5 3
5 2
4 3
4 2
3 1
2 1
1 8
5
8 7 5 2 1
output
0 3

Problem solving

刚开始看到这道题的时候一点都不想看，因为太长了。仔细看了一下，这道题的意思就是给你一个有向图，现在有一个系统会自动给出你所在的位置到达终点的最短路的路径，如果你下一步走的不是系统给出的最短路的路径，系统会重新规划一次，起点为你现在的位置，现在给出你走的路径，问系统最多最少重新规划几次。
首先我们要知道当你走的路不是系统规划的最短路的时候就会重新规划。因为最短路并不是唯一的，所以会存在不一样的规划次数。
最小的规划次数就是每次你走的都是规划的最短路。
最大的规划次数就是每次走只要存在可以重新规划的下一步就重新规划。
因为每次系统规划的都是到达终点的最短路，所以我们需要从终点开始倒着bfs。统计出来每个点到终点的最短距离。并且我们走的路径是固定的，所以从起点开始每次比较当前点和下一个走到的点到终点的距离。再根据上面两个条件计算min和max即可。具体细节详见代码注释。

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
#define pb push_back
typedef long long ll;
vector<int> v1[maxn], v2[maxn];
int a[maxn], dis[maxn], vis[maxn];
void bfs(int x)
{
    queue<int> que;

    que.push(x); vis[x] = 1;
    while (!que.empty()) {
        int mid = que.front();
        que.pop();
        for (int i = 0; i < v2[mid].size(); i++) {
            int p = v2[mid][i];
            if (vis[p]) continue;
            vis[p] = 1;
            dis[p] = dis[mid] + 1;
            que.push(p);
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    int n, m, k;
    cin >> n >> m;
    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        v1[u].pb(v); v2[v].pb(u);//有向图存的时候存单向边即可。v2存反边，为下面求每个点到终点的最短路做准备
    }
    cin >> k;
    for (int i = 1; i <= k; i++)
        cin >> a[i];
    bfs(a[k]);//求出其他点到终点的最短路
    // for (int i = 1; i <= n; i++) cout << i << " " << dis[i] << endl;
    int minn = 0, maxx = 0;
    for (int i = 1; i < k; i++)
        if (dis[a[i]] - 1 != dis[a[i + 1]]) minn++;//最少重新规划次数的情况，只要每走一步接近终点一步，就不需要重新规划，否则重新规划，这是必须的，因为规划的最短路中不会出现距离终点距离一样的。
    for (int i = 1; i < k; i++) {
        int flag = 0, mid = a[i];
        for (int j = 0; j < v1[mid].size(); j++) {
            int mi = v1[mid][j];
            if (mi != a[i + 1] && dis[mi] + 1 == dis[mid]) flag = 1;
            if (mi == a[i + 1] && dis[mi] + 1 != dis[mid]) flag = 1;
            /*
            最多规划次数的情况，遍历跟这个点相连的所有点，我们假设这个点为mi点，如果mi点不是我们要走的路径中的下一个点
            并且"dis[mi]+1==dis[mid]"，那我们就可以假设之前规划的最短路是经过这个点的，
            但是走到下一个点并不是规划的这个点，需要重新规划一次。或者mi点就是我们要走的路径中的下一个点，
            并且这个点跟上一个点到终点的距离相等，那么我们也需要重新规划一次，这个在最少的情况种已经解释过了。
            */
        }
        if (flag) maxx++;
    }
    cout << minn << " " << maxx << endl;
}

News

经历了不知道多久的py以及py，我的cf1700分了！！！虽然有水分，但是还是吹自己一波2333