Hướng dẫn giải của HSG12 Tây Ninh 2026 - Vòng 1 - Bài 2
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 làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả:
Ta nhận xét như sau:
- Nếu đi chung tốt hơn, ta sẽ luôn cố gắng đi chung đến hết, hay nói cách khác, ta sẽ chọn một đỉnh ~i~ và đi riêng từ ~1 \rightarrow i~, ~2 \rightarrow i~, và đi chung từ ~i \rightarrow n~. Ta sẽ BFS từ ~1~, từ ~2~ và từ ~n~ để tính đường đi từ ~i \rightarrow n~.
- Nếu đi riêng tốt hơn, ta sẽ đi riêng từ ~1 \rightarrow n~ và ~2 \rightarrow n~ (luôn có thể vì ta được phép đợi).
Độ phức tạp: ~O(n + m)~.
Code tham khảo
void BFS(int u, vector<int> &dist, const vector<vector<int>> &G) {
dist[u] = 0;
queue<int> q;
q.push(u);
while(!q.empty()) {
int u = q.front(); q.pop();
for(int v : G[u]) if (dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
void solve() {
int n, b, e, p, m;
cin >> b >> e >> p >> n >> m;
vector<vector<int>> G(n + 5);
while(m--) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
vector<int> dist1(n + 5, 27092008), dist2(n + 5, 27092008), dist3(n + 5, 27092008);
BFS(1, dist1, G);
BFS(2, dist2, G);
BFS(n, dist3, G);
long long ans = 1LL * dist1[n] * b + 1LL * dist2[n] * e;
for(int i = 1; i <= n; i++) ans = min(ans, 1LL * dist1[i] * b + 1LL * dist2[i] * e + 1LL * dist3[i] * p);
cout << ans;
}
Bình luận