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

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
struct node{
    int u,r,t;
    bool operator<(const node& other)const{
        return t>other.t;
    }
};
int main(){
    freopen("bus.in","r",stdin);
    freopen("bus.out","w",stdout);
    int n,m,k;
    cin>>n>>m>>k;
    vector<vector<pair<int,int> > > graph(n+1);
    for(int i=0;i<m;i++){
        int u,v,a;
        cin>>u>>v>>a;
        graph[u].push_back(make_pair(v,a));
    }
    vector<vector<int> > dist(n+1,vector<int>(k,INF));
    dist[1][0]=0;
    priority_queue<node> q;
    q.push((node){1,0,0});
    while(!q.empty()){
        node cur=q.top();
        q.pop();
        int u=cur.u,r=cur.r,t=cur.t;
        if(t>dist[u][r])continue;
        for(int i=0;i<graph[u].size();i++){
            int v=graph[u][i].first;
            int a=graph[u][i].second;
            int new_t,new_r;
            if(t<a){
                int x=(a-t+k-1)/k;
                new_t=t+1+x*k;
            }else{
                new_t=t+1;
            }
            new_r=(r+1)%k;
            if(new_t<dist[v][new_r]){
                dist[v][new_r]=new_t;
                q.push((node){v,new_r,new_t});
            }
        }
    }
    if(dist[n][0]==INF)cout<<-1<<endl;
    else cout<<dist[n][0]<<endl;
    return 0;
}