Codeforces 238E Meeting Her 圖論 + 記憶化搜索 最壞情況換乘

問題大意

有向圖 n≤100，k≤100 條公交線路。第 i 路線從 s_i 到 t_i，每秒隨機選一條最短路徑行駛。Urpal 從 a 到 b，可在任意交叉點上/下車。已知圖結構和所有 (s_i, t_i)。求最壞情況下最少換乘次數（不可達輸出 -1）。

核心觀察：公交車必經節點

對路線 (s,t)，某節點 v 在所有 s→t 最短路徑上 ⇔ dist[s][v] + dist[v][t] == dist[s][t] 且 dist[s][v] 唯一遞增。這些節點形成一條「必經鏈」。

兩階段解法

1. Floyd 計算全源最短路 dist[u][v]
2. 構建必經關係：對每條路線 i，標記 on_route[i][v] = true 若 v 在所有最短路上
3. 記憶化搜索 DP：
   • f[v]：從 v 到 b 的最優策略（最少換乘）
   • g[v]：最壞情況下從 v 到 b 仍需換乘次數
   • 遞歸：g[v] = min( f[v], max_{u 必經且更近} g[u] )

關鍵代碼框架

const int MAXN = 105, INF = 0x3f3f3f3f;
int dist[MAXN][MAXN];
bool on_route[105][MAXN];
int f[MAXN], g[MAXN];
bool vis[MAXN];
int n, m, a, b, k;
int S[105], T[105];

int dfs(int u) {
    if (u == b) return f[u] = 0;
    if (vis[u]) return g[u];
    vis[u] = true;
    g[u] = INF;

    // 選擇不坐車直接走？題目必須坐車，故考慮所有路線
    for (int i = 1; i <= k; ++i) {
        if (!on_route[i][u]) continue;
        // 從 u 坐路線 i，最壞情況被送到哪個下一必經點？
        int worst = 0;
        for (int v = 1; v <= n; ++v) {
            if (on_route[i][v] && dist[u][v] == 1 && dist[S[i]][v] == dist[S[i]][u] + 1) {
                worst = max(worst, dfs(v));
            }
        }
        g[u] = min(g[u], worst + 1); // 換乘一次
    }
    return g[u];
}

複雜度與細節

• Floyd：O(n³) = 10⁶
• 必經點判定：O(k·n²)
• DP 狀態 n，每狀態枚舉 k·n，總 O(k·n²) ≈ 10⁶
• 環檢測：vis 標記避免無限遞歸
• 不可達：最終 g[a] >= INF 輸出 -1