题解 100% AC

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
vector<pair<int, int>> g[N];
int dis[N][105];
bool vis[N][105];
int n,m,k,u,v,w;
struct node{
    int u,t,dis;
    bool operator<(const node &a) const{return dis > a.dis;}
};
priority_queue<node> q;
void bfs(){
    memset(dis,0x3f,sizeof(dis));
    q.push({1,0,dis[1][0]=0});
    while(!q.empty()){
        node head=q.top();
        q.pop();
        if(vis[head.u][head.t])continue;
        vis[head.u][head.t]=1;
        for(int i=0;i<g[head.u].size();i++){
            v=g[head.u][i].first,w=g[head.u][i].second;
            int tu=dis[head.u][head.t],tv=(head.t+1)%k;
            if(tu<w)tu+=(w-tu+k-1)/k*k;
            if(dis[v][tv]>tu+1){
                dis[v][tv]=tu+1;
                q.push({v,tv,dis[v][tv]});
            }
        }
    }
}
int main(){
    freopen("bus.in","r",stdin);
    freopen("bus.out","w",stdout);
    cin>>n>>m>>k;
    for (int i = 1; i <= m; i++){
        cin>>u>>v>>w;
        g[u].push_back(make_pair(v, w));
    }
    bfs();
    cout<<(dis[n][0] == 0x3f3f3f3f ? -1 : dis[n][0]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}