Codeforces Round #625 (Div. 1) B. Navigation System (R1800)

似たようなことは考えたことがあった。経路復元に関する理解を問う教育的問題！

問題へのリンク

問題概要

重みなしの有向グラフと、2 頂点 s, t を始点と終点にもつパスが与えられる。今、われわれはナビに沿ってこのパスをたどっている。ナビの仕様は次の通りだ

• 今いる頂点 v から終点 t に向かう最短路のうち、いずれか 1 つを選ぶ
• そのパスにおいて、v の次の頂点を w としたとき
• 「次の頂点」として w を指示する

パスの移動中において、ナビの指示した通りに移動しなかった回数として考えられるもののうち、最小値と最大値を求めよ。

制約

• 頂点数, 辺数

考えたこと

これは考えたことがあった！！！
一般に、二頂点 s, t を結ぶ最短路をすべて列挙することは難しい。しかし、次のことは簡単にできるのだ！！！

---

今いる頂点 v から終点 t へ向かう最短路をすべて考えたときの、「v の次の頂点」として考えられるものをすべて列挙する

---

これができれば、この問題を解くのは簡単だ。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using Graph = vector<vector<int>>;
int N, M;
Graph G;
vector<int> path;

vector<set<int> > pre;
vector<int> dist;
void solve() {
    int s = path[0], t = path.back();
    queue<int> que;
    que.push(t);
    dist[t] = 0;
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (auto nv : G[v]) {
            if (dist[nv] != -1) {
                if (dist[nv] == dist[v] + 1) pre[nv].insert(v);
                continue;
            }
            dist[nv] = dist[v] + 1;
            pre[nv].insert(v);
            que.push(nv);
        }
    }
    int ma = 0, mi = 0;
    for (int i = 0; i+1 < path.size(); ++i) {
        // mi
        if (!pre[path[i]].count(path[i+1])) ++mi;

        // ma
        if (!(pre[path[i]].size() == 1 && *pre[path[i]].begin() == path[i+1])) ++ma;
    }
    cout << mi << " " << ma << endl;
}

int main() {
    while (scanf("%d %d", &N, &M) != EOF) {
        G.assign(N, vector<int>());
        for (int i = 0; i < M; ++i) {
            int u, v;
            scanf("%d %d", &u, &v);
            --u, --v;
            //G[u].push_back(v);
            G[v].push_back(u);
        }
        dist.assign(N, -1);
        pre.assign(N, set<int>());
        int K; scanf("%d", &K);
        path.assign(K, 0);
        for (int i = 0; i < K; ++i) scanf("%d", &path[i]), --path[i];
        solve();
    }
}