Mô tả bài toán
Có n ga, m đường ray hai chiều. Từ ga j, tàu khởi hành đi các ga liền kề tại các bội số của k_j, mỗi chuyến mất t_j thời gian. Tìm thời gian sớm nhất đến ga dst từ src (bỏ qua thời gian chuyển tàu).
Ví dụ
n=4,m=3,src=1,dst=4, roads={{1,2},{2,4},{3,4}}, departure={{2,1},{3,5},{7,6}}. Đầu ra: 8.
Thuật toán (Dijkstra biến đổi)
- Xây đồ thị: mỗi cạnh lưu
(đích, t, k). - Mảng
dplưu thời gian đến sớm nhất (khởi tạo -∞). - Hàng đợi ưu tiên max-heap theo
-time(vì muốn lấy thời gian nhỏ nhất). - Khi ở ga
alúcw, tàu đến gablúcweight = ceil((w+1)/k)*k - t(công thức trong code). - Cập nhật
dp[b]nếuweight > dp[b](lưu ý dấu âm trong heap).
Đoạn mã C++
#include <bits/stdc++.h>
using namespace std;
int solve(int n, int m, int src, int dst,
vector<pair<int,int>> roads,
vector<pair<int,int>> departure) {
src--; dst--;
vector<tuple<int,int,int>> graph[n];
for(int i=0;i dp[b]) {
dp[b]=weight;
pq.push({weight, b});
}
}
}
return -1;
}
int main() {
int n=4,m=3,src=1,dst=4;
vector<pair<int,int>> roads={{1,2},{2,4},{3,4}};
vector<pair<int,int>> departure={{2,1},{3,5},{7,6}};
cout << solve(n,m,src,dst,roads,departure);
return 0;
}
Đầu vào / Đầu ra
Input: 4, 3, 1, 4, {{1,2},{2,4},{3,4}}, {{2,1},{3,5},{7,6}}
Output: 8