Hướng dẫn giải của [Trại hè HV 2025 Tin 10] ROAD
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
Quang đi xe đạp từ 1 đến ~N~ và chở Vinh đến một địa điểm ~v~ nào đó; từ ~v~ Vinh tự đi bộ đến ~K~ (Vinh có thể không đi nhờ chút nào, tức ~v = 1~). Với một ~v~ cố định, Quang nên đi đường xe đạp ngắn nhất từ 1 đến ~v~ rồi đường xe đạp ngắn nhất từ ~v~ đến ~N~. Điều kiện cho Vinh: ~\text{bike}(1,v) + \text{walk}(v,K) \le X~. Thời gian của Quang là ~\text{bike}(1,v) + \text{bike}(v,N)~; chọn ~v~ nhỏ nhất, không có ~v~ hợp lệ thì in ~-1~. Kiểm tra ví dụ: ~v = 2~ cho ~1 + 3 = 4 \le 4~ và Quang mất ~1 + 2 = 3~.
Sub 1: Dijkstra quét mảng — ~O(N^2 + M)~, dùng khi ~N \le 1000~
Chạy ba lần Dijkstra: xe đạp từ 1; đi bộ về ~K~ (trên đồ thị đảo chiều cạnh); xe đạp về ~N~ (trên đồ thị đảo chiều). Rồi duyệt mọi ~v~. Nếu chỉ nộp sub này: đúng 12/40 test.
Sub 2: Dijkstra với hàng đợi ưu tiên — ~O(M \log N)~
Cùng ý tưởng nhưng mỗi lần Dijkstra dùng ~priority_queue~. Khoảng cách dùng ~long long~. Nếu chỉ nộp sub này: đúng 40/40 test.
Chương trình hoàn chỉnh
Hàm main đọc file ROAD.INP, ghi ROAD.OUT; ~N \le 1000~ gọi sub1 (12 test), lớn hơn gọi sub2 (28 test). Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)4e18;
int N, M, K;
ll X;
struct Edge { int to, a, b; };
vector<Edge> g[100005], rg[100005];
// Dijkstra dùng hàng đợi ưu tiên: adj là đồ thị, w = 0 chọn trọng số a (đi bộ), w = 1 chọn b (xe đạp)
vector<ll> dijkstra(int src, vector<Edge> *adj, int w) {
vector<ll> d(N + 1, INF);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
d[src] = 0; pq.push({0, src});
while (!pq.empty()) {
auto [du, u] = pq.top(); pq.pop();
if (du > d[u]) continue;
for (auto &e : adj[u]) {
ll c = du + (w ? e.b : e.a);
if (c < d[e.to]) { d[e.to] = c; pq.push({c, e.to}); }
}
}
return d;
}
// Dijkstra O(N^2) bằng quét mảng — dùng khi N <= 1000
vector<ll> dijkstraSlow(int src, vector<Edge> *adj, int w) {
vector<ll> d(N + 1, INF);
vector<char> done(N + 1, 0);
d[src] = 0;
for (int it = 0; it < N; it++) {
int u = 0;
for (int i = 1; i <= N; i++)
if (!done[i] && (u == 0 || d[i] < d[u])) u = i;
if (u == 0 || d[u] == INF) break;
done[u] = 1;
for (auto &e : adj[u]) d[e.to] = min(d[e.to], d[u] + (w ? e.b : e.a));
}
return d;
}
// Quang chở Vinh theo đường ngắn nhất bằng xe đạp từ 1 đến một địa điểm v, rồi Vinh đi bộ từ v đến K.
// Cần: bike(1,v) + walk(v,K) <= X. Quang tới N mất bike(1,v) + bike(v,N). Chọn v tối thiểu hóa.
void solve(bool slow) {
auto run = [&](int s, vector<Edge> *adj, int w) { return slow ? dijkstraSlow(s, adj, w) : dijkstra(s, adj, w); };
vector<ll> b1 = run(1, g, 1); // xe đạp từ 1 tới v
vector<ll> wk = run(K, rg, 0); // đi bộ từ v tới K (Dijkstra trên đồ thị ngược)
vector<ll> bn = run(N, rg, 1); // xe đạp từ v tới N
ll ans = INF;
for (int v = 1; v <= N; v++) {
if (b1[v] == INF || wk[v] == INF || bn[v] == INF) continue;
if (b1[v] + wk[v] <= X) ans = min(ans, b1[v] + bn[v]);
}
cout << (ans == INF ? -1 : ans) << "\n";
}
// Sub 1: Dijkstra O(N^2) — dùng khi N <= 1000
void sub1() { solve(true); }
// Sub 2: Dijkstra với hàng đợi ưu tiên — O(M log N)
void sub2() { solve(false); }
int main() {
freopen("ROAD.INP", "r", stdin);
freopen("ROAD.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> N >> M >> K >> X;
for (int i = 0; i < M; i++) {
int u, v, a, b; cin >> u >> v >> a >> b;
g[u].push_back({v, a, b});
rg[v].push_back({u, a, b});
}
if (N <= 1000) sub1();
else sub2();
return 0;
}
Bình luận