【題解】Codeforces 1321D. Navigation System

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define F first
#define S second
 
const int maxn = 2e5+5;
int n, m, a, b, s, t, dis[maxn], pl, p[maxn], mn_ans, mx_ans;
vector <int> v[maxn], v2[maxn];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        cin >> a >> b;
        v[b].push_back(a);
        v2[a].push_back(b);
    }
    cin >> pl;
    for (int i = 0; i < pl; i++){
        cin >> p[i];
    }
    s = p[0];
    t = p[pl-1];
    priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    pq.push({0, t});
    memset(dis, -1, sizeof(dis));
    pair<int, int> now;
    while (!pq.empty()){
        now = pq.top();
        pq.pop();
        if (dis[now.S] != -1) continue;
        dis[now.S] = now.F;
        for (int nxt:v[now.S]){
            pq.push({now.F+1, nxt});
        }
    }
    for (int i = 1; i < pl-1; i++){
        int mn = dis[p[i]]+1;
        for (int nxt:v2[p[i-1]]){
            if (nxt == p[i]) continue;
            mn = min(mn, dis[nxt]);
        }
        if (mn < dis[p[i]]) mn_ans++;
        if (mn <= dis[p[i]]) mx_ans++;
    }
    cout << mn_ans << " " << mx_ans << "\n";
}