HDU 3143 Speedy Escape：最短路 + 路徑記錄 + 二分/比率優化

HDU 3143：搶劫犯與警察同時從不同起點出發，搶劫犯速度可控，警察固定 160 km/h。搶劫犯需到達任意高速公路出口，且全程不被警察追上（同一時間同一地點即被捕）。求搶劫犯最小最高速度。

關鍵洞察

1. 搶劫犯路徑固定後，警察會選擇最短路徑攔截
2. 對於搶劫犯路徑上任意點 X，設搶劫犯距離 d_r(X)，警察距離 d_p(X)
3. 為不被追上：d_r(X) / v_r < d_p(X) / 160 → v_r > 160 * d_r(X) / d_p(X)
4. 所需最小速度 = 路徑上所有點的 max(160 * d_r / d_p)

算法流程

1. 計算警察從 P 到所有點的最短距離 dist_p[] (Dijkstra)
2. 計算搶劫犯從 B 到所有點的最短距離 dist_r[]，**但必須繞過警察起點 P** (修改版 Dijkstra，禁止經過 P)
3. 記錄搶劫犯最短路徑樹（前驅節點 pre[]）
4. 對每個出口 E，若可達 (dist_r[E] < INF)，回溯路徑 E → ... → B
5. 對路徑上每個節點 u，計算所需速度 v_u = 160 * dist_r[u] / dist_p[u]（若 dist_p[u] == INF 則警察不可達，速度為 0）
6. 該出口所需速度 = 路徑上最大 v_u
7. 答案 = 所有可達出口中最小速度

關鍵實現細節

Dijkstra 記錄路徑

vector<int> pre(n+1, -1);
priority_queue<pair<double,int>, vector<pair<double,int>>, greater<>> pq;
dist[src] = 0;
pq.push({0, src});

while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;
    for (auto [v, w] : adj[u]) {
        if (v == police) continue; // 搶劫犯繞過警察起點
        if (dist[v] > dist[u] + w) {
            dist[v] = dist[u] + w;
            pre[v] = u; // 記錄前驅
            pq.push({dist[v], v});
        }
    }
}

速度計算

double ans = INF;
for (int exit : exits) {
    if (dist_r[exit] == INF) continue; // 不可達
    
    double need = 0;
    for (int u = exit; u != -1; u = pre[u]) {
        if (dist_p[u] < INF) { // 警察可達此點
            need = max(need, 160.0 * dist_r[u] / dist_p[u]);
        }
    }
    ans = min(ans, need);
}

if (ans == INF) cout << "IMPOSSIBLE\n";
else cout << fixed << setprecision(10) << ans << '\n';

完整 AC 代碼架構

#include <bits/stdc++.h>
using namespace std;
const double INF = 1e100;
const int MAXN = 105;

struct Edge { int to, len; };
vector<Edge> adj[MAXN];
double dist_p[MAXN], dist_r[MAXN];
int pre[MAXN];
bool is_exit[MAXN];

void dijkstra(int src, double dist[], int avoid = -1) {
    fill(dist, dist + MAXN, INF);
    fill(pre, pre + MAXN, -1);
    dist[src] = 0;
    priority_queue<pair<double,int>, vector<pair<double,int>>, greater<>> pq;
    pq.push({0, src});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto &e : adj[u]) {
            int v = e.to;
            if (v == avoid) continue;
            if (dist[v] > dist[u] + e.len) {
                dist[v] = dist[u] + e.len;
                pre[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, e;
    while (cin >> n >> m >> e) {
        for (int i = 1; i <= n; ++i) {
            adj[i].clear();
            is_exit[i] = false;
        }
        
        for (int i = 0; i < m; ++i) {
            int a, b, l;
            cin >> a >> b >> l;
            adj[a].push_back({b, l});
            adj[b].push_back({a, l});
        }
        
        for (int i = 0; i < e; ++i) {
            int x; cin >> x; is_exit[x] = true;
        }
        int B, P; cin >> B >> P;
        
        dijkstra(P, dist_p);       // 警察最短路
        dijkstra(B, dist_r, P);    // 搶劫犯繞過 P
        
        double ans = INF;
        for (int i = 1; i <= n; ++i) if (is_exit[i] && dist_r[i] < INF) {
            double need = 0;
            for (int u = i; u != -1; u = pre[u]) {
                if (dist_p[u] < INF)
                    need = max(need, 160.0 * dist_r[u] / dist_p[u]);
            }
            ans = min(ans, need);
        }
        
        if (ans == INF) cout << "IMPOSSIBLE\n";
        else cout << fixed << setprecision(10) << ans << '\n';
    }
    return 0;
}

複雜度分析

• Dijkstra：O(m log n)，兩次
• 路徑回溯：O(n × 出口數) ≤ O(n²)
• 總體：O(m log n)，n ≤ 100, m ≤ 5000 極快

關鍵注意點

1. 搶劫犯**必須繞過警察起點 P**，不能經過 P（否則起始即被捕）
2. 道路長度單位是「百米」，速度計算時單位自動抵消，無需換算
3. 若警察無法到達路徑上某點 (dist_p[u] == INF)，該點不構成速度限制
4. 精度要求 1e-6，雙精度 double 足夠，輸出 10 位小數保險
5. 圖為無向連通圖，邊權為正

此題將「雙源最短路 + 路徑重建 + 比率優化」巧妙結合，是圖論綜合應用的優秀範例。