Hướng dẫn giải của Trại đông Bảo Lộc 2021 - Xe buýt liên tỉnh
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ả: ,
Nhận thấy khi mua hệ thống xe ở thành phố ~i~, thì ta có thể sử dụng miễn phí ~d_i~ chuyến xe tiếp theo.
Gọi ~f[u][x]~ là chi phí nhỏ nhất để đến thành phố ~u~ và còn được miễn phí ~x~ chuyến nữa.
Chuyển trạng thái từ thành phố ~u~ sang ~v~:
- Nếu ~d > 0~, ~f[v][x - 1] = f[u][x]~.
- ~f[v][d_v] = f[u][x] + c_v~.
Sử dụng thuật toán dijkstra để tìm đường đi ngắn nhất từ ~1~ đến ~n~.
Độ phức tạp: ~O(n^2 + m.log_2(n^2))~.
Code tham khảo:
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> Q;
memset(dist, 0x3f, sizeof dist);
dist[1][d[1]] = c[1];
Q.push({c[1], d[1], 1});
while(!Q.empty()) {
auto T = Q.top(); Q.pop();
int cost = T[0], u = T[2], free = T[1];
if (cost != dist[u][free]) continue;
if (u == n) {
cout << cost;
return;
}
if (free == 0) continue;
for(int v : G[u]) {
if (minimize(dist[v][free - 1], cost)) // continue
Q.push({cost, free - 1, v});
if (minimize(dist[v][d[v]], cost + c[v])) // buy new
Q.push({cost + c[v], d[v], v});
}
}
Bình luận