ABC021 C問題：正直者の高橋くん

問題. 正直者の高橋くん

$n$ 頂点の連結無向グラフ $G = (V, E)$ が与えられる． $a \in V$ から $b \in V$ への最短経路数を答えよ．

制約： $2 \le n \le 100$

解法1. 最短経路木

$a$ から各頂点 $v \in V$ への最短距離を $d(v)$ とする．このとき， $G$ の最短経路木 $T = (V, A)$ とは頂点集合が $G$ と等しく，弧集合が $A = \{(u, v) \mid d(v) = d(u) + 1\}$ となる有向グラフのことである．また， $T$ は有向閉路が存在しない DAG なのでトポロジカルソート $v_{i_1}, v_{i_2}, \ldots, v_{i_n}$ が存在する． $G$ 上の任意の最短経路は必ず $T$ の弧を通るので， $f(v)$ を $a$ から $v$ への最短経路数と定義すると，
　　 $f(v_i) = \sum_{j < i \, \wedge \, (v_j, v_i) \in A} f(v_j)$
となる．
各頂点への最短距離は幅優先探索で $O(n + m)$ 時間で求め（ $m = |E|$ ），トポロジカルソートと漸化式 $f$ の更新は $T$ 上の入次数で行い $O(n + m)$ 時間で求めた．

計算時間： $O(n + m)$

解法1のソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
constexpr ll MOD = 1e9 + 7;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n, a, b, m;
    cin >> n >> a >> b >> m;

    --a; --b;
    vector<vector<int>> adj(n);
    for (int i = 0, x, y; i < m; ++i) {
        cin >> x >> y;
        adj[x - 1].push_back(y - 1);
        adj[y - 1].push_back(x - 1);
    }

    vector<int> d(n, -1);
    queue<int> que;
    for (que.push(a), d[a] = 0; !que.empty(); ) {
        const int v = que.front(); que.pop();
        for (int u : adj[v])
            if (d[u] == -1) {
                d[u] = d[v] + 1;
                que.push(u);
            }
    }

    vector<int> in_deg(n);
    for (int v = 0; v < n; ++v) {
        for (int u : adj[v])
            if (d[v] == d[u] + 1) ++in_deg[v];
        if (in_deg[v] == 0) que.push(v);
    }

    vector<ll> cnt(n);
    for (cnt[a] = 1; !que.empty(); ) {
        const int v = que.front(); que.pop();
        for (int u : adj[v]) {
            if (d[u] == d[v] + 1) {
                (cnt[u] += cnt[v]) %= MOD;
                --in_deg[u];
                if (in_deg[u] == 0) que.push(u);
            }
        }
    }
    cout << cnt[b] << endl;

    return 0;
}

解法2. 隣接行列の冪乗

$G$ の隣接行列 $A \in \mathbb{R}^{n \times n}$ とは， $\{u, v\} \in E$ のとき $A_{u v} = 1$ ， $\{u, v\} \notin E$ のとき $A_{u v} = 0$ で定義される行列のことである．任意の非負整数 $k$ に対して $A^k_{u, v}$ は頂点 $u$ から $v$ への長さ $k$ の歩道の数と等しい（ $k$ による帰納法で示せる）．ここで，歩道とは頂点の重複と辺の重複を許す道のことである．
$A^k_{a b}$ が非零となる最小の $k$ と， $a$ から $b$ への最短距離は等しく，そのときの $A^k_{a b}$ の値が $a$ から $b$ への最短経路数となる． $a$ から $b$ への最短距離は高々 $n - 1$ なので，愚直に計算しても $O(n^4)$ 時間で答えが求まる．

計算時間： $O(n^4)$

解法2のソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
constexpr ll MOD = 1e9 + 7;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n, a, b, m;
    cin >> n >> a >> b >> m;

    --a; --b;
    vector<vector<ll>> adj(n, vector<ll>(n));
    for (int i = 0, x, y; i < m; ++i) {
        cin >> x >> y;
        adj[x - 1][y - 1] = adj[y - 1][x - 1] = 1;
    }

    vector<vector<ll>> cnt = adj;
    while (cnt[a][b] == 0) {
        vector<vector<ll>> nxt(n, vector<ll>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < n; ++k) {
                    (nxt[i][j] += (adj[i][k] * cnt[k][j]) % MOD) %= MOD;
                }
            }
        }
        cnt = nxt;
    }

    cout << cnt[a][b] << endl;

    return 0;
}

今回の問題の重み付き ver. は最短距離を求める部分で計算時間が異なるだけで本質的には同じ計算で答えが求まる．