HDU 3143 Speedy Escape——二分答案 + SPFA + DFS 可行性判定

問題背景

兄弟要逃離城市，有 n 個路口、m 條雙向道路（長度為整數）、e 個出口。警察局位於 pli，兄弟起點 bro。兄弟車速可調，警察車速固定 160。求兄弟最小車速，使得存在一條從 bro 到任意出口的路徑，滿足：對路徑上任意點，兄弟到達時間 嚴格小於 警察到達同點時間。若無解輸出 IMPOSSIBLE。

核心觀察

• 兄弟到達某點的時間 = 路徑長度 / v_bro；警察到達時間 = 警察最短路長度 / 160。
• 條件轉化為：路徑長度 / v_bro < 警察最短路 / 160 ⇔ v_bro > 160 × (路徑長度 / 警察最短路)。
• 對於固定 v_bro，判定是否存在合法路徑：從 bro 出發 DFS，只走滿足「當前累積長度 × 160 < v_bro × 警察最短路[當前點]」的邊，且不能經過警察局。若能到達任一出口則可行。
• v_bro 越大條件越寬鬆，具有單調性 → 二分答案。

算法流程

1. 跑兩次 SPFA（或 Dijkstra，邊權非負）：
   • 從 bro 出發，禁經 pli，得 `distBro[u]` = 兄弟到 u 的最短路。
   • 從 pli 出發，得 `distPolice[u]` = 警察到 u 的最短路。
2. 二分車速 `v` ∈ [0, 1e7]，精度 1e-6：
   • 中間值 `mid`，DFS 判定可行性：`vis` 數組防環，遞歸條件 `distBro[now] * mid < distPolice[now] * 160.0`。
   • 若可行則 `r = mid`，否則 `l = mid`。
3. 若最終不可行輸出 IMPOSSIBLE，否則輸出 `mid`（保留 10 位小數）。

關鍵代碼片段

bool dfs(int u) {
    vis[u] = true;
    if (distBro[u] * mid >= distPolice[u] * 160.0) return false; // 不滿足時間條件
    if (isExit[u]) return true; // 到達出口
    for (auto [v, w] : adj[u]) {
        if (!vis[v] && dfs(v)) return true;
    }
    return false;
}

bool check(double v) {
    mid = v;
    memset(vis, 0, sizeof(vis));
    return dfs(bro);
}

// 主函數二分
double l = 0, r = 1e7;
while (r - l > 1e-6) {
    double mid = (l + r) / 2;
    if (check(mid)) r = mid;
    else l = mid;
}

易錯點提醒

• SPFA 禁經警察局：兄弟最短路計算時不能經過 pli，否則兄弟可能「穿過」警察局，邏輯不通。
• Double 比較：題目精度低（1e-5 即可過），但建議用 1e-6 並採用 `<` 而非 `<=`，避免邊界浮點誤差。
• 圖的建模：道路雙向，邊權為長度。出口標記數組 `isExit[]`。
• 無解判定：二分結束後若 `check(r)` 仍 false，輸出 IMPOSSIBLE。

複雜度

• SPFA：O(k·m) 期望線性，n≤100, m≤10000 極快。
• DFS 判定：O(n+m) 每次。
• 二分約 50 次迭代，總體毫秒級。

總結

本題是「二分答案 + 圖論最短路 + DFS 可行性檢查」的經典組合。關鍵在於將「兄弟必須比警察早到」轉化為路徑長度不等式，利用單調性二分車速。SPFA 計算兩套最短路是預處理核心，DFS 剪枝判定利用預計算的距離數組極為高效。