Hướng dẫn giải của [KS cụm QL] Câu 4: Du lịch
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 một hành trình xuất phát từ địa điểm nổi tiếng, thăm đủ ~K~ địa điểm nổi tiếng (~K \le 7~) với chi phí nhỏ nhất, trong đó mỗi lần tới một địa điểm nổi tiếng mới (kể cả điểm xuất phát) thì có thêm một phiếu giảm giá: có ~T~ phiếu thì giá mỗi vé là ~\lfloor c \cdot (10 - T) / 10 \rfloor~. Nhận xét chính: chi phí chỉ đổi khi đến điểm nổi tiếng mới, nên hành trình được xác định bởi thứ tự thăm lần đầu các điểm nổi tiếng, còn giữa hai lần thăm liên tiếp thì đi theo đường ngắn nhất với số phiếu ~T~ hiện có. Điểm xuất phát tính là có 1 phiếu (ví dụ: ~1 \to 2 \to 3 \to 4 \to 5~ có giá ~0 + 1 + 2 + 3 = 6~).
Chuẩn bị: với mỗi ~T = 1..K~ và mỗi điểm nổi tiếng ~i~, chạy Dijkstra (đồ thị có hướng, giá vé đã giảm) để có ~D_T[i][j]~. Việc đó mất ~K^2~ lần Dijkstra, rất nhanh với ~N \le 2000~, ~M \le 10000~.
Sub 1: Vét cạn mọi thứ tự — ~O(K! \cdot K)~, dùng khi ~K \le 6~
Thử mọi hoán vị các điểm nổi tiếng, chi phí là tổng ~D_t[p_{t-1}][p_t]~ với ~t = 1, 2, \dots~. Nếu có đoạn không tới được thì bỏ qua; không có hoán vị nào hợp lệ thì in ~-1~. Nếu chỉ nộp sub này: đúng 21/21 test (các test đều có ~K \le 7~ nhỏ nên vẫn kịp).
Sub 2: Quy hoạch động bitmask — ~O(2^K \cdot K^2)~
Gọi ~dp[mask][i]~ là chi phí nhỏ nhất khi đã thăm tập ~mask~ các điểm nổi tiếng và đang ở ~i~; số phiếu bằng số bit 1 của ~mask~. Chuyển sang điểm ~j~ chưa thăm với chi phí ~D_{|mask|}[i][j]~. Đáp án là giá trị nhỏ nhất của ~dp[2^K - 1][i]~, hoặc ~-1~. Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu (đọc/ghi file CAU4.INP/CAU4.OUT), tính các bảng ~D~; nếu ~K \le 6~ gọi sub1, ngược 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. Kết quả: 21/21 test.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N, M, K;
vector<array<int,2>> adj[2005]; // (đỉnh đến, giá vé gốc), có hướng
vector<int> fam; // các địa điểm nổi tiếng (đã bỏ trùng)
const ll INF = 1e18;
ll D[8][8][8]; // D[T][i][j]: chi phí ngắn nhất từ nổi tiếng i đến j khi có T phiếu giảm giá
// Dijkstra từ s khi có T phiếu: giá vé mỗi đường = floor(c * (10 - T) / 10)
vector<ll> dijkstra(int s, int T) {
vector<ll> d(N + 1, INF);
priority_queue<pair<ll,int>, vector<pair<ll,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] : adj[u]) {
ll nd = du + c * (10 - T) / 10;
if (nd < d[v]) { d[v] = nd; pq.push({nd, v}); }
}
}
return d;
}
// Sub 1: thử mọi thứ tự thăm lần đầu các địa điểm nổi tiếng — O(K! * K), dùng khi K <= 6
// Đoạn từ điểm nổi tiếng thứ t đến thứ t+1 đi theo đường ngắn nhất với t phiếu giảm giá.
void sub1() {
int k = fam.size();
vector<int> p(k);
iota(p.begin(), p.end(), 0);
ll best = INF;
do {
ll cost = 0;
for (int t = 1; t < k && cost < INF; t++) {
ll d = D[t][p[t - 1]][p[t]];
if (d >= INF) cost = INF; else cost += d;
}
best = min(best, cost);
} while (next_permutation(p.begin(), p.end()));
cout << (best >= INF ? -1 : best) << "\n";
}
// Sub 2: quy hoạch động bitmask — O(2^K * K^2)
// dp[mask][i] = chi phí nhỏ nhất đã thăm tập mask các điểm nổi tiếng, đang ở i; số phiếu = số bit của mask
void sub2() {
int k = fam.size();
vector<vector<ll>> dp(1 << k, vector<ll>(k, INF));
for (int i = 0; i < k; i++) dp[1 << i][i] = 0;
for (int mask = 1; mask < (1 << k); mask++) {
int T = __builtin_popcount(mask);
for (int i = 0; i < k; i++) {
if (dp[mask][i] >= INF) continue;
for (int j = 0; j < k; j++) {
if (mask >> j & 1 || D[T][i][j] >= INF) continue;
int nm = mask | 1 << j;
dp[nm][j] = min(dp[nm][j], dp[mask][i] + D[T][i][j]);
}
}
}
ll best = INF;
for (int i = 0; i < k; i++) best = min(best, dp[(1 << k) - 1][i]);
cout << (best >= INF ? -1 : best) << "\n";
}
int main() {
freopen("CAU4.INP", "r", stdin);
freopen("CAU4.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> N >> M >> K;
for (int i = 0; i < M; i++) {
int u, v, c1, c2; cin >> u >> v >> c1 >> c2;
adj[u].push_back({v, c1});
adj[v].push_back({u, c2});
}
for (int i = 0; i < K; i++) { int x; cin >> x; fam.push_back(x); }
sort(fam.begin(), fam.end());
fam.erase(unique(fam.begin(), fam.end()), fam.end());
int k = fam.size();
for (int T = 1; T <= k; T++)
for (int i = 0; i < k; i++) {
vector<ll> d = dijkstra(fam[i], T);
for (int j = 0; j < k; j++) D[T][i][j] = d[fam[j]];
}
if (K <= 6) sub1();
else sub2();
return 0;
}
Bình luận