HDU 2962 完整解析：限高條件下的最短路二分

圖中每條邊有長度和限高。車輛高度固定，只能通過限高 ≥ 車高的邊。求最大可通行高度下的最短路徑長度。若無法到達輸出 cannot reach destination。

核心策略：二分車高 + SPFA 判斷連通性

二分搜尋高度 H（範圍 0~給定上限）。檢查函數：構建只含限高 ≥ H 的邊的子圖，跑 SPFA 判斷 S 能否達到 T 及最短距離。

完整 AC 程式碼

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;
const int INF = 1e9;

int n, m;
int h[MAXN][MAXN], len[MAXN][MAXN];
int d[MAXN];
bool inq[MAXN];
int mid_h;

void spfa(int s) {
    fill(d, d + n + 1, INF);
    fill(inq, inq + n + 1, false);
    queue q;
    d[s] = 0; q.push(s); inq[s] = true;
    
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (int v = 1; v <= n; v++) {
            if (h[u][v] >= mid_h && h[u][v] != -1) { // 滿足限高
                if (d[v] > d[u] + len[u][v]) {
                    d[v] = d[u] + len[u][v];
                    if (!inq[v]) { q.push(v); inq[v] = true; }
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tc = 1;
    while (cin >> n >> m, n || m) {
        // 初始化
        for (int i = 1; i <= n; i++) {
            fill(h[i], h[i] + n + 1, -1);
            fill(len[i], len[i] + n + 1, INF);
        }
        
        for (int i = 0; i < m; i++) {
            int a, b, hh, ll;
            cin >> a >> b >> hh >> ll;
            len[a][b] = len[b][a] = ll;
            h[a][b] = h[b][a] = hh;
        }
        
        int S, T, H_max;
        cin >> S >> T >> H_max;
        
        int L = 0, R = H_max;
        int best_h = 0, best_len = INF;
        
        while (L <= R) {
            mid_h = (L + R) / 2;
            spfa(S);
            
            if (d[T] == INF) {
                R = mid_h - 1; // 太高了，降低
            } else {
                if (mid_h > best_h || (mid_h == best_h && d[T] < best_len)) {
                    best_h = mid_h;
                    best_len = d[T];
                }
                L = mid_h + 1; // 嘗試更高
            }
        }
        
        if (tc > 1) cout << '\n';
        cout << "Case " << tc++ << ":\n";
        if (best_h == 0) cout << "cannot reach destination\n";
        else {
            cout << "maximum height = " << best_h << '\n';
            cout << "length of shortest route = " << best_len << '\n';
        }
    }
    return 0;
}

關鍵點總結

• 二分單調性：高度越高，可用邊越少，最短距離單調不減（或不可達）
• 同高度取最短：二分過程中記錄最佳高度對應的最短距離
• 輸出格式：Case 編號、空行分隔、不可達特殊輸出
• 邊存儲：鄰接矩陣存限高與長度，-1 表示無邊