問題描述
無向圖 n≤1000 點，m 條邊。每邊有長度 `w` 和限高 `h`。給起點 s、終點 e、車輛最大高度 `lim`。求：在高度 ≤ `lim` 的道路中，從 s 到 e 的最短路徑長度，及該最短路徑中允許的最大高度（即路徑上邊的最小 `h`，但不超過 `lim`）。無路輸出 "cannot reach destination"。
二分高度 + Dijkstra
- 二分答案 `H ∈ [0, lim]`：檢查只走 `h ≥ H` 的邊，是否能從 s 到 e。
- 檢查函數：Dijkstra 求 s 到 e 最短路，邊權 `w`，忽略 `h < H` 的邊。
- 二分找到最大可行 `H`，對應的最短路即為答案。
代碼實現
#include
using namespace std;
const int MAXN = 1010;
const int INF = 1e9;
struct Edge { int v, h, w; };
vector G[MAXN];
int dist[MAXN];
bool vis[MAXN];
int n, m, s, e, lim;
bool dijkstra(int H) {
fill(dist, dist+n+1, INF);
fill(vis, vis+n+1, false);
dist[s] = 0;
priority_queue, vector>, greater>> pq;
pq.emplace(0, s);
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (vis[u]) continue;
vis[u] = true;
if (u == e) return true;
for (auto& ed : G[u]) {
if (ed.h < H) continue;
int v = ed.v, nd = d + ed.w;
if (nd < dist[v]) {
dist[v] = nd;
pq.emplace(nd, v);
}
}
}
return false;
}
int main() {
int tc = 0;
while (cin >> n >> m, n || m) {
for (int i = 1; i <= n; ++i) G[i].clear();
for (int i = 0; i < m; ++i) {
int u, v, h, w; cin >> u >> v >> h >> w;
if (h == -1) h = INF; // 無限高
G[u].push_back({v, h, w});
G[v].push_back({u, h, w});
}
cin >> s >> e >> lim;
int L = 0, R = lim, bestH = -1, bestDist = -1;
while (L <= R) {
int mid = (L + R) >> 1;
if (dijkstra(mid)) {
bestH = mid;
bestDist = dist[e];
L = mid + 1;
} else R = mid - 1;
}
if (tc++) cout << '\n';
cout << "Case " << ++tc << ":\n";
if (bestH == -1) cout << "cannot reach destination\n";
else {
cout << "maximum height = " << bestH << '\n';
cout << "length of shortest route = " << bestDist << '\n';
}
}
return 0;
}
關鍵點
- 二分單調性：允許高度越低，可用邊越多，最短路長度單調不增，可行性單調（高→低由不可行變可行）。
- Dijkstra 優先隊列：n=1000, m≤?，堆優化 O(m log n) 極快。
- 無限高處理：輸入 `h=-1` 視為 `INF`，不限制高度。
- 輸出格式：Case 編號、空行分隔、固定字符串。
複雜度
- 二分 log(lim) ≤ 30 次（lim≤10⁹），每次 Dijkstra O(m log n)。
- 總計 O(log lim · m log n) ≈ 30 × 10⁴ × 10 = 3×10⁶，極快。
總結
「限高條件下的最短路」→ 二分高度閾值 + Dijkstra 判定連通性。二分找最大可行高度，對應的最短路即答案。經典「二分答案 + 圖論判定」模板。
