簡易題敘#
有 \(n\) ( \(2 \le n \le 10^5\) ) 個節點、 \(m\) ( \(1 \le m \le 10^5\) ) 條帶權有向邊，第 \(i\) 條邊的起點終點權重分別是 \(a_i\)、 \(b_i\) ( \(1 \le a_i < b_i \le n\) ) 跟 \(c_i\) ( \(0 \le c_i \le 10^9\) ) ，求一條從點 \(1\) 到點 \(n\) 的路徑，最多包含 \(d\) 條邊，且最小化圖上最大權重。
範例測資：
- 輸入
4 5 2
1 2 5
2 3 3
1 3 7
2 4 6
3 4 4
- 輸出
2
1 2 4
概念講解#
我們拿圖上最大權重二分搜，因此在輸入的時候就要記錄整張圖上的最大權重當我們二分搜的右界。
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
graph[a].push_back({b, c});
max_c = max(max_c, c);
}
每次都跑一次 BFS ( 詳見後章 )，因為題目要求輸出路徑，所以還要再開一個 vector path紀錄路徑，dist紀錄最短距離，parent記錄這個點是從哪來的，這樣之後才能回溯路徑。
如果這條道路的權重不超過目前的權重限制，而且走這條路不會使總路程超過允許走的路數，並且這是到達下一個城市目前找到的最短路徑，那麼我們就選擇這條路，然後更新它的資訊。
if (weight <= max_weight && dist[curr] + 1 <= d && dist[next] > dist[curr] + 1) {
dist[next] = dist[curr] + 1;
parent[next] = curr;
q.push(next);
}
跑完 BFS 結果根本沒走到終點就是 false：
if (dist[n] == INT_MAX) return false;
否則開始回朔路徑，塞進path
path.clear();
for (int v = n; v != -1; v = parent[v]) {
path.push_back(v);
}
reverse(path.begin(), path.end());
return true;
範例程式碼#
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, m, d;
vector<pair<int, int>> graph[MAXN];
vector<int> path;
bool bfs(int max_weight) {
vector<int> dist(n + 1, INT_MAX);
vector<int> parent(n + 1, -1);
queue<int> q;
q.push(1);
dist[1] = 0;
while (!q.empty()) {
int curr = q.front();
q.pop();
if (curr == n) break;
for (auto& edge : graph[curr]) {
int next = edge.first, weight = edge.second;
if (weight <= max_weight && dist[curr] + 1 <= d && dist[next] > dist[curr] + 1) {
dist[next] = dist[curr] + 1;
parent[next] = curr;
q.push(next);
}
}
}
if (dist[n] == INT_MAX) return false;
path.clear();
for (int v = n; v != -1; v = parent[v]) {
path.push_back(v);
}
reverse(path.begin(), path.end());
return true;
}
int main() {
cin >> n >> m >> d;
int max_c = 0;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
graph[a].push_back({b, c});
max_c = max(max_c, c);
}
int left = 0, right = max_c, result = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (bfs(mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
if (result == -1) {
cout << -1 << endl;
} else {
cout << path.size() - 1 << endl;
for (int v : path) {
cout << v << " ";
}
cout << endl;
}
}
