思路
直接建分層圖即可,每個點的狀態都可以表示模 \(k\) 意義下的時間,因此每個點可以拆成 \(k\) 個, 然后我們在跑Dijkstar就行了
Code
#include <bits/stdc++.h>
#define r(x, y) ((x) * (n + 1) + (y))
#define ss second
#define ff first
using i64 = long long;
typedef std::pair<int, int> PII;
const int N = 4e6 + 10;
int n, m, k, f[N];
bool st[N];
std::vector<std::pair<int, int>> G[N];
/*
設到到達s的最小時間為x
則有 x + 0, x + 1, x + 2, ... , x + k - 1 情況
我們設f[i][s] 表示第i種到達s的最小花費時間
考慮如何轉移:
考慮存在邊 u->s, s的點權重為a
若f[i][s] + 1 < a, 那么我們需要等待 f[i] + 1 + nk >= a 時間, 取最小的n
若f[i][s] + 1 > a
*/
void dijkstra() {
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> h1;
memset(f, 0x3f, sizeof f);
// 先傳入 0s 進入 第1個點
f[r(0, 1)] = 0;
h1.push({0, r(0, 1)});
while (h1.size()) {
auto t = h1.top(); h1.pop();
i64 u = t.ss % (n + 1);
// std::cout << u << "\n";
if (st[t.ss]) continue;
st[t.ss] = true;
for (auto x: G[u]) {
i64 tim = f[t.ss] + 1;
// std::cout << x.ff << "\n";
// 如果到達時, 該邊還未開放
if (x.ss > t.ff) {
// 向上取整
tim += (x.ss - f[t.ss] + (k - 1)) / k * k;
}
if (f[r(tim % k, x.ff)] > tim) {
f[r(tim % k, x.ff)] = tim;
h1.push({tim, r(tim % k, x.ff)});
}
}
}
}
int main() {
std::cin >> n >> m >> k;
while (m --) {
int u, v, a; std::cin >> u >> v >> a;
G[u].push_back({v, a});
}
// if (n == 1) {
// std::
// }
dijkstra();
if (f[r(0, n)] == 0x3f3f3f3f) {
return puts("-1"), 0;
}
std::cout << f[r(0, n)];
}
浙公網安備 33010602011771號