95分求调

#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define fo(i,a,b) for(int i=(a);i<(b);++i)
using namespace std;
const int N=2e4+5;
#define PII pair<int,int>

int n,m,k;
vector<PII> G[N];

void add(int x,int y,int e){
    G[x].push_back({y,e});
}

int f[N][105];
int vis[N][105];

signed main(){
    cin>>n>>m>>k;
    rep(i,1,m){
        int x,y,e;
        cin>>x>>y>>e;
        add(x,y,e);
    }
    memset(f,0x3f,sizeof f);
    queue<PII> q;q.push({1,0});
    f[1][0]=0;vis[1][0]=1;

    while(q.size()){
        int u=q.front().first,p=q.front().second;
        q.pop();vis[u][p]=0;
        int pp=f[u][p];
        for(auto d:G[u]){
            int v=d.first,w=d.second,t;
            if(pp>=w) t=pp;
            else t=((w-pp+k-1)/k)*k+pp;
            if(f[v][(t+1)%k]>t+1){
                f[v][(t+1)%k]=t+1;
                if(!vis[v][(t+1)%k]){
                    vis[v][(t+1)%k]=1;
                    q.push({v,(t+1)%k});
                }
            }
        }
    }
    cout<<f[n][0];
}