Hướng dẫn giải của [2526 KSCUM_PN] Câu 4: Titan
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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.
Hướng dẫn giải
Cần tìm số cạnh ít nhất trên đường đi từ trạm t đến trạm k, hoặc in "Titan" nếu không có đường. Đây là bài tìm đường đi ngắn nhất trên đồ thị không trọng số.
Sub 1: Duyệt mọi đường đi đơn — ~O(\text{số đường đi đơn})~, dùng khi ~n \le 10~
DFS từ t trên các đỉnh chưa thăm, ghi lại độ dài nhỏ nhất khi tới k, cắt nhánh khi đã dài hơn đáp án tốt nhất. Đúng 12/12 test.
Sub 2: BFS — ~O(n + m)~
Duyệt theo chiều rộng từ t, khoảng cách tới k chính là số cạnh ít nhất. Nếu k không được thăm thì in "Titan". Đúng 12/12 test.
Chương trình hoàn chỉnh
Hàm main đọc n, m, t, k và các cạnh. Nếu n \le 10 gọi sub 1, còn lại gọi sub 2.
#include <bits/stdc++.h>
using namespace std;
int n, m, t, k;
vector<vector<int>> g;
// Sub 1: duyệt mọi đường đi đơn (DFS) từ t, ghi lại độ dài ngắn nhất tới k. Dùng khi n <= 10.
int best1 = INT_MAX;
vector<char> onPath;
void dfs(int u, int len) {
if (len >= best1) return; // cắt nhánh: đã dài hơn đáp án tốt nhất
if (u == k) {
best1 = len;
return;
}
for (int w : g[u])
if (!onPath[w]) {
onPath[w] = 1;
dfs(w, len + 1);
onPath[w] = 0;
}
}
void sub1() {
onPath.assign(n + 1, 0);
onPath[t] = 1;
dfs(t, 0);
if (best1 == INT_MAX) cout << "Titan\n";
else cout << best1 << "\n";
}
// Sub 2: BFS từ t, O(n + m). Số cạnh ít nhất đi từ t đến k chính là khoảng cách BFS.
void sub2() {
vector<int> dist(n + 1, -1);
queue<int> q;
dist[t] = 0;
q.push(t);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int w : g[u])
if (dist[w] == -1) {
dist[w] = dist[u] + 1;
q.push(w);
}
}
if (dist[k] == -1) cout << "Titan\n";
else cout << dist[k] << "\n";
}
int main() {
freopen("CAU4.INP", "r", stdin);
freopen("CAU4.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> t >> k;
g.assign(n + 1, {});
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
if (n <= 10) sub1();
else sub2();
return 0;
}
Bình luận