Hướng dẫn giải của Lộ trình hợp lý (đề chọn HSG QG Tuyên Quang 2024)
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
Cuội đạp xe từ 1 đến N, đến một địa điểm ~p~ nào đó thì cho Hằng Nga xuống, Hằng Nga đi bộ từ ~p~ đến ~K~ và phải đến nơi không muộn hơn thời điểm ~X~. Ta cần chọn ~p~ sao cho tổng thời gian của Cuội (đạp xe 1 → ~p~ → N) nhỏ nhất.
Sub 1: Floyd-Warshall — ~O(N^3)~, dùng khi ~N \le 100~
Tính ma trận đường đi ngắn nhất theo xe đạp ~b~ và theo đi bộ ~w~ giữa mọi cặp đỉnh. Thử mọi ~p~: nếu ~b[1][p] + w[p][K] \le X~ thì ứng viên là ~b[1][p] + b[p][N]~. Nếu chỉ nộp sub này: đúng 10/30 test.
Sub 2: Dijkstra — ~O(M \log N)~
Chỉ cần ba đường đi ngắn nhất: xe đạp từ 1 (đồ thị thuận), xe đạp tới N (chạy trên đồ thị đảo chiều từ N), đi bộ tới ~K~ (đồ thị đảo chiều từ ~K~). Sau đó duyệt mọi ~p~ như sub 1. Chú ý ~p~ có thể là 1 (Hằng Nga đi bộ từ đầu) hoặc N; nếu không có ~p~ hợp lệ thì in -1. Dữ liệu thực tế có ~M~ lớn hơn 10^5 nên mảng cạnh cần để dư. Nếu chỉ nộp sub này: đúng 30/30 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu; ~N \le 100~ thì gọi sub1, còn lại gọi sub2. 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;
const long long INF = 1e18;
int n, m, K;
long long X;
int U[400005], V[400005], A[400005], B[400005];
// Sub 1: Floyd-Warshall O(N^3), dùng khi N <= 100
void sub1() {
static long long b[105][105], w[105][105];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) b[i][j] = w[i][j] = (i == j ? 0 : INF);
for (int i = 0; i < m; i++) {
b[U[i]][V[i]] = min(b[U[i]][V[i]], (long long)B[i]);
w[U[i]][V[i]] = min(w[U[i]][V[i]], (long long)A[i]);
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (b[i][k] < INF && b[k][j] < INF) b[i][j] = min(b[i][j], b[i][k] + b[k][j]);
if (w[i][k] < INF && w[k][j] < INF) w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
}
long long best = INF;
for (int p = 1; p <= n; p++)
if (b[1][p] < INF && w[p][K] < INF && b[p][n] < INF && b[1][p] + w[p][K] <= X)
best = min(best, b[1][p] + b[p][n]);
printf("%lld\n", best >= INF ? -1LL : best);
}
vector<pair<int,int>> g[3][400005];
vector<long long> dij(int t, int s) {
vector<long long> d(n + 1, INF);
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
d[s] = 0; pq.push({0, s});
while (!pq.empty()) {
auto [du, u] = pq.top(); pq.pop();
if (du > d[u]) continue;
for (auto [v, c] : g[t][u]) if (d[v] > du + c) { d[v] = du + c; pq.push({d[v], v}); }
}
return d;
}
// Sub 2: 3 lần Dijkstra O(M log N)
void sub2() {
for (int i = 0; i < m; i++) {
g[0][U[i]].push_back({V[i], B[i]}); // xe đạp, đồ thị thuận
g[1][V[i]].push_back({U[i], B[i]}); // xe đạp, đồ thị ngược
g[2][V[i]].push_back({U[i], A[i]}); // đi bộ, đồ thị ngược
}
auto d1 = dij(0, 1); // xe đạp từ 1 tới p
auto dn = dij(1, n); // xe đạp từ p tới N
auto wk = dij(2, K); // đi bộ từ p tới K
long long best = INF;
for (int p = 1; p <= n; p++)
if (d1[p] < INF && dn[p] < INF && wk[p] < INF && d1[p] + wk[p] <= X)
best = min(best, d1[p] + dn[p]);
printf("%lld\n", best >= INF ? -1LL : best);
}
int main() {
freopen("Lotrinh.inp", "r", stdin);
freopen("Lotrinh.out", "w", stdout);
scanf("%d %d %d %lld", &n, &m, &K, &X);
for (int i = 0; i < m; i++) scanf("%d %d %d %d", &U[i], &V[i], &A[i], &B[i]);
if (n <= 100) sub1();
else sub2();
return 0;
}
Bình luận