【題目敘述】http://codeforces.com/contest/1321/problem/D
【解題想法】Dijkstra algorithm 找最短路徑
#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";
}