思路

直接建分層圖即可，每個點的狀態都可以表示模 \(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)];
}