记录编号	607309	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3930.[CSP 2023J]旅游巴士	最终得分	100
用户昵称	金牌教师王艳芳	是否通过	通过
代码语言	C++	运行时间	0.865 s
提交时间	2025-10-09 23:33:27	内存使用	7.19 MiB

#include<bits/stdc++.h>
using namespace std;
int main(){
    freopen("bus.in","r",stdin);
    freopen("bus.out","w",stdout);
    int n,m,k;
    cin>>n>>m>>k;
    int u[20005],v[20005],a[20005];
    vector<int> g[10005];
    for(int i=0;i<m;i++){
        cin>>u[i]>>v[i]>>a[i];
        g[u[i]].push_back(i);
    }
    int d[10005][105];
    for(int i=1;i<=n;i++)for(int j=0;j<k;j++)d[i][j]=1000000000;
    d[1][0]=0;
    queue<pair<int,int>> q;
    q.push(make_pair(1,0));
    while(!q.empty()){
        int cu=q.front().first,cr=q.front().second;
        q.pop();
        for(int i=0;i<g[cu].size();i++){
            int e=g[cu][i],nv=v[e],na=a[e],ct=d[cu][cr];
            int nt=ct;
            if(nt<na){
                int x=(na-nt+k-1)/k;
                nt+=x*k;
            }
            nt++;
            int nr=(cr+1)%k;
            if(nt<d[nv][nr]){
                d[nv][nr]=nt;
                q.push(make_pair(nv,nr));
            }
        }
    }
    if(d[n][0]==1000000000)cout<<-1<<endl;
    else cout<<d[n][0]<<endl;
    return 0;
}