Hướng giải của Đồ thị lưới hiểm trở
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Bài toán này yêu cầu cài đặt cải tiến SLF (Small Label First) cho thuật toán SPFA.
Kỹ thuật SLF sử dụng hàng đợi song hướng std::deque thay vì std::queue. Khi một đỉnh \(v\) được cập nhật và cần đẩy vào hàng đợi:
- Nếu hàng đợi không rỗng và \(dist[v] < dist[dq.front()]\), ta đẩy \(v\) vào đầu hàng đợi bằng
push_front. - Ngược lại, ta đẩy \(v\) vào cuối hàng đợi bằng
push_back. Điều này giúp tối ưu hóa số lượng đỉnh cần cập nhật lại và ngăn chặn việc bị rơi vào độ phức tạp tệ nhất trên đồ thị Grid hiểm trở.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, s;
if (!(cin >> n >> m >> s)) return 0;
vector<vector<pair<int, long long>>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
long long w;
if (cin >> u >> v >> w) {
adj[u].push_back({v, w});
}
}
vector<long long> dist(n + 1, INF);
vector<bool> in_queue(n + 1, false);
dist[s] = 0;
deque<int> dq;
dq.push_back(s);
in_queue[s] = true;
while (!dq.empty()) {
int u = dq.front();
dq.pop_front();
in_queue[u] = false;
for (auto& edge : adj[u]) {
int v = edge.first;
long long w = edge.second;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (!in_queue[v]) {
if (!dq.empty() && dist[v] < dist[dq.front()]) {
dq.push_front(v);
} else {
dq.push_back(v);
}
in_queue[v] = true;
}
}
}
}
for (int i = 1; i <= n; i++) {
if (dist[i] == INF) cout << -1 << (i == n ? "" : " ");
else cout << dist[i] << (i == n ? "" : " ");
}
cout << "\n";
return 0;
}
Nhận xét