拆点+dijkstra

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10000;
const int MAXK = 100;
const int INF = 2147483647;
int n, m, k;
vector<pair<int, int>> e[MAXN + 5];
int dis[MAXN + 5][MAXK + 5];
bool vis[MAXN + 5][MAXK + 5];
priority_queue<pair<int, pair<int, int>>> pq;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
    {
        int u, v, a;
        cin >> u >> v >> a;
        e[u].push_back({v, a});
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= k - 1; j++)
            dis[i][j] = INF;
    dis[1][0] = 0;
    pq.push({-0, {1, 0}});
    while (!pq.empty())
    {
        int u = pq.top().second.first;
        int uu = pq.top().second.second;
        pq.pop();
        if(vis[u][uu])
            continue;
        vis[u][uu] = true;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int a = e[u][i].second;
            int w = 1;
            if (dis[u][uu] < a)
                w = (a - dis[u][uu] + (k - 1)) / k * k + 1;
            int vv = (dis[u][uu] + w) % k;
            if (dis[u][uu] + w < dis[v][vv])
            {
                dis[v][vv] = dis[u][uu] + w;
                pq.push({-dis[v][vv], {v, vv}});
            }
        }
    }
    if (dis[n][0] == INF)
        cout << "-1";
    else
        cout << dis[n][0];
    return 0;
}

拆点+二分答案

略