记录编号	583874	评测结果	AAAWWAAWWWAAAWWWWWWW
题目名称	[CSP 2023J]旅游巴士	最终得分	40
用户昵称	在大街上倒立游泳	是否通过	未通过
代码语言	C++	运行时间	0.511 s
提交时间	2023-10-23 21:07:50	内存使用	11.79 MiB

#include<bits/stdc++.h>
using namespace std;
struct ngm{
    long long i,j,d;
    friend bool operator < (ngm a,ngm b){
        return a.d<b.d;
    }
};
typedef long long ll;
ll f[10010][110],lian[20010],xia[20010],tot=0,w[20010],n,m,k,head[10010];
bool vis[10010][110];
queue<ngm> dui;
void add(ll x,ll y,ll v){
	tot++;
	xia[tot]=head[x];
	head[x]=tot;
	lian[tot]=y;
	w[tot]=v;
}
void dfs(ll p,ll mo){
	ll xian=head[p];
	while(lian[xian]){
		ll ans=f[p][mo]+1;
		if(ans<=w[xian]){
			ans+=(((w[xian]-ans)/k)*k);
			if(ans<=w[xian]) ans+=k;
		}
		if(f[lian[xian]][(mo+1)%k]==-1){
			f[lian[xian]][(mo+1)%k]=ans;
			dfs(lian[xian],(mo+1)%k);
		}
		else{
			if(ans<f[lian[xian]][(mo+1)%k]){
				f[lian[xian]][(mo+1)%k]=ans;
				dfs(lian[xian],(mo+1)%k);
			}
		}
		xian=xia[xian]; 
	}
}
void djstl(){
    while(!dui.empty()){
        ngm xin=dui.front();
        //cout<<xin.i<<' '<<xin.j<<' '<<xin.d<<endl;
        dui.pop();
        if(vis[xin.i][xin.j]) continue;
        vis[xin.i][xin.j]=1;
        long long xian=head[xin.i];
        while(lian[xian]){
            long long t=xin.d;
            if(t<w[xian]){
                t+=((w[xian]-t)/k)*k+(((w[xian]-t)%k)?k:0);
            }
            t++;
            
            if(!vis[lian[xian]][(xin.d+1)%k]&&t<f[lian[xian]][(xin.d+1)%k]){
                //cout<<"*"<<lian[xian]<<' '<<(xin.d+1)%k<<' '<<t<<endl;
                f[lian[xian]][(xin.d+1)%k]=t;
                dui.push({lian[xian],(xin.d+1)%k,t});
            }
            xian=xia[xian];
        }
    }
}
int main(){
	freopen("bus.in","r",stdin);
	freopen("bus.out","w",stdout);
	scanf("%lld%lld%lld",&n,&m,&k);
	for(ll i=1;i<=m;i++){
		ll u,v,a;
		scanf("%lld%lld%lld",&u,&v,&a);
		add(u,v,a);
	}
	memset(f,0x3f,sizeof(f));
	f[1][0]=0;
	//vis[1][0]=1;
	dui.push({1,0,0});
	djstl();
	if(f[n][0]==0x3f3f3f3f3f3f3f3f) f[n][0]=-1;
   	printf("%lld",f[n][0]);
	return 0;
}