献上本人代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
const int N=1e4+5,M=2*1e4+5;
vector<pll>E[M];
priority_queue<pll,vector<pll>,greater<pll> >q;
ll dp[N][M];
bool f[N][M];
int n,m,k;
inline ll read(){
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch&15),ch=getchar();
	return x*f;
} 
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
void dijkstra(ll s){
	q.push(make_pair(0,s));
	while(!q.empty()){
		ll u=q.top().second,w=q.top().first;
		if(f[u][w%k])continue;
		f[u][w%k]=1;
		for(int i=0;i<E[u].size();i++){
			ll v=E[u][i].second,p=E[u][i].first;
			ll t;
			if(p>=w)t=p;
			else t=((w-p+k-1)/k)*k+p;
			if(dp[v][(t+1)%k]>t+1){
				dp[v][(t+1)%k]=t+1;
				q.push(make_pair(t+1,v));
			}
		}
		q.pop();
	}
}
int main(){
	
	n=read(),m=read(),k=read();
	for(int i=0;i<m;++i){
		int u,v,w;
		u=read(),v=read(),w=read();
		E[u].push_back(make_pair(v,w));
	}
	dijkstra(1);
	if(!dp[n][0]){
		write(-1);
	}else write(dp[n][0]);
	return 0;
}

谢谢