TLE求条

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
#define pii pair <int, int>
#define mk make_pair
#define ps push
int n, m, k;
struct way {
    int to, w;
};
vector <way> G[N];
int dis[N][110];
/*
dis[i][j] 表示到达i这个位置，时刻%k后是j
*/
void dij () {
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < k; j++) {
            dis[i][j] = INT_MAX;
        }
    }
    dis[1][0] = 0;
    priority_queue <pii, vector <pii>, greater <pii> > q;
    q.ps (mk (0, 1));
    while (!q.empty ()) {
        auto [z, u] =  q.top (); q.pop ();
        for (auto [v, w] : G[u]) {
            for (int i = 0; i < k; i++) {
                if (dis[u][i] == INT_MAX) continue;
                if (dis[u][i] >= w) {
                    if (dis[v][(i + 1) % k] < dis[u][i] + 1) continue;
                    dis[v][(i + 1) % k] = dis[u][i] + 1;
                    q.ps (mk (dis[v][(i + 1) % k], v));
                } else {
                    if (dis[v][(i + 1) % k] < dis[u][i] + ceil ((w - dis[u][i]) * 1.0 / k) * k + 1) continue;
                    dis[v][(i + 1) % k] = dis[u][i] + ceil ((w - dis[u][i]) * 1.0 / k) * k + 1;
                    q.ps (mk (dis[v][(i + 1) % k], v));
                }
            }
        }
    }
    if (dis[n][0] == INT_MAX) dis[n][0] = -1;
    cout << dis[n][0] << "\n";
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        G[u].push_back ({v, w});
    }
    dij ();
	return 0;
}