Hướng dẫn giải của Truyền tin trong mạng
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tìm đường đi có tổng chi phí (trọng số) nhỏ nhất từ máy nguồn S đến máy đích T trong một mạng gồm N máy tính và M kênh truyền thông hai chiều. Mỗi kênh nối hai máy Di và Ci có chi phí truyền tin G_i. Đây là bài toán tìm đường đi ngắn nhất (Shortest Path) trên đồ thị có trọng số không âm, có thể sử dụng thuật toán Dijkstra.
Các cách tiếp cận
Cách Dijkstra (Bản gốc)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 100001;
int n, m, s, t;
vector<pair<int, int>> adj[maxn];
void nhap(){
cin >> n >> m >> s >> t;
for(int i = 0; i < m; i++){
int x, y, w; cin >> x >> y >> w;
adj[x].push_back({y, w});
adj[y].push_back({x, w});
}
}
const int INF = 1e9;
void dijkstra(int s, int t){
vector<ll> d(n + 1, INF);
d[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> Q;
Q.push({0, s});
while(!Q.empty()){
pair<int, int> top = Q.top(); Q.pop();
int u = top.second;
int kc = top.first;
if(kc > d[u]) continue;
for(auto it : adj[u]){
int v = it.first;
int w = it.second;
if(d[v] > d[u] + w){
d[v] = d[u] + w;
Q.push({d[v], v});
}
}
}
cout << d[t];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
nhap();
dijkstra(s, t);
return 0;
}
- Time Complexity: O(M log N)
- Space Complexity: O(N + M)
Đây là cách tiếp cận tiêu chuẩn. Sử dụng hàng đợi ưu tiên (min-heap) để lấy ra đỉnh có khoảng cách nhỏ nhất chưa xét. Với mỗi đỉnh, ta duyệt các đỉnh kề và cập nhật khoảng cách. Độ phức tạp là O(M log N) do mỗi cạnh được xử lý tối đa một lần và thao tác với hàng đợi ưu tiên tốn O(log N).
Cách Dijkstra (Tối ưu bộ nhớ)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxn = 1e4 + 5;
ll n, m, s, e;
vector<pair<ll, ll>> v[maxn];
void Init() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
}
void nhap() {
cin >> n >> m >> s >> e;
ll x, y, w;
for (ll i = 1; i <= m; i++) {
cin >> x >> y >> w;
v[x].push_back({y, w});
v[y].push_back({x, w});
}
}
void dijkstra(ll x) {
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
vector<ll> dis(n + 1, LONG_MAX);
dis[x] = 0;
pq.push({0, x});
while (!pq.empty()) {
pair<ll, ll> top = pq.top(); pq.pop();
ll u = top.second; ll kc = top.first;
if (kc > dis[u]) continue;
for (auto it : v[u]) {
ll node = it.first;
ll cost = it.second;
if (dis[node] > dis[u] + cost) {
dis[node] = dis[u] + cost;
pq.push({dis[node], node});
}
}
}
cout << dis[e];
}
int main() {
Init();
nhap();
dijkstra(s);
return 0;
}
- Time Complexity: O(M log N)
- Space Complexity: O(N + M)
Giải thuật tương tự cách 1 nhưng được tối ưu hóa về mặt khai báo biến và thư viện. Việc sử dụng 'long long' cho khoảng cách đảm bảo không bị tràn số (overflow) với các chi phí lớn. Sử dụng 'LONG_MAX' để khởi tạo khoảng cách vô cùng.
Cách Dijkstra với lưu đường đi
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 100001;
int n, m, s, t;
vector<pair<int, int>> adj[maxn];
int pre[maxn]; // Mảng lưu cha để truy vết đường đi
void nhap(){
cin >> n >> m >> s >> t;
for(int i = 0; i < m; i++){
int x, y, w; cin >> x >> y >> w;
adj[x].push_back({y, w});
adj[y].push_back({x, w});
}
}
const int INF = 1e9;
void dijkstra(int s, int t){
vector<ll> d(n + 1, INF);
d[s] = 0;
pre[s] = -1;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> Q;
Q.push({0, s});
while(!Q.empty()){
pair<int, int> top = Q.top(); Q.pop();
int u = top.second;
int kc = top.first;
if(kc > d[u]) continue;
for(auto it : adj[u]){
int v = it.first;
int w = it.second;
if(d[v] > d[u] + w){
d[v] = d[u] + w;
pre[v] = u; // Ghi nhận rằng đường đi ngắn nhất đến v đi qua u
Q.push({d[v], v});
}
}
}
cout << d[t];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
nhap();
dijkstra(s, t);
return 0;
}
- Time Complexity: O(M log N)
- Space Complexity: O(N + M)
Biến bổ sung 'pre[]' được dùng để lưu lại đỉnh cha của mỗi đỉnh trên đường đi ngắn nhất. Mặc dù bài này chỉ yêu cầu in ra chi phí, nhưng đây là kỹ thuật phổ biến khi cần in ra hoặc reconstruct đường đi. Logic thuật toán Dijkstra vẫn giữ nguyên.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(M log N) | O(N + M) | Dijkstra (Bản gốc) |
| 2 | O(M log N) | O(N + M) | Dijkstra (Tối ưu bộ nhớ) |
| 3 | O(M log N) | O(N + M) | Dijkstra với lưu đường đi |
Bài học kinh nghiệm
- Bài toán này là bài toán tìm đường đi ngắn nhất cơ bản trên đồ thị có hướng/ vô hướng với trọng số không âm.
- Sử dụng 'long long' cho khoảng cách và 'priority_queue' (min-heap) là yêu cầu bắt buộc để xử lý hiệu quả và tránh tràn số.
- Đồ thị có thể có đến 100,000 cạnh, do đó độ phức tạp O(M log N) của Dijkstra là phù hợp, trong khi các thuật toán như Bellman-Ford (O(NM)) sẽ quá chậm.
Lỗi thường gặp
- Tràn số số nguyên (Integer Overflow): Chi phí các cạnh lên tới 30,000 và có thể có nhiều cạnh trên đường đi. Nếu dùng 'int' để tính tổng chi phí, có thể bị tràn số. Phải dùng 'long long'.
- Quên xử lý đồ thị vô hướng: Input là các cạnh hai chiều, cần thêm cạnh vào cả hai phía (adj[x] -> y và adj[y] -> x).
- Khởi tạo sai giá trị vô cùng: Nếu giá trị INF quá nhỏ so với tổng chi phí thực tế, thuật toán có thể sai. Nên dùng giá trị lớn như 1e18 hoặc LONG_MAX.
- Truy cập ngoài mảng: Đỉnh số thứ tự từ 1 đến N, cần khai báo mảng/vector có kích thước N+1.
Bình luận