太简单

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+5,K = 105,inf = 0x3f3f3f3f;
int hd[N],cnt,f[N][K],n,m,k;
bool vis[N][K];
struct node{int to,nex,w;}e[N << 1];
void add(int u,int v,int w)
{e[cnt] = {v,hd[u],w};hd[u] = cnt;}
queue<pair<int,int> > q;
void spfa()
{
memset(f,inf,sizeof f);f[1][0] = 0;
vis[1][0] = 1;q.push(make_pair(1,0));
while(!q.empty())
{
int u = q.front().first,x = q.front().second;
q.pop();vis[u][x] = 0;
for(int i = hd[u];i;i = e[i].nex)
{
int v = e[i].to,w = e[i].w,p = f[u][x],y = (x+1)%k;
int c = p < w?p+((w-p-1)/k+1)k:p;
if(c+1 < f[v][y])
{
f[v][y] = c+1;
if(!vis[v][y])vis[v][y] = 1,q.push(make_pair(v,y));
}
}
}
}
inline int rd()
{
char c;int f = 1;
while(!isdigit(c = getchar()))if(c=='-')f = -1;
int x = c-'0';
while(isdigit(c = getchar()))x = x10+(c^48);
return x*f;
}
int main()
{
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
n = rd();m = rd();k = rd();
for(int i = 1;i <= m;i)
{int u = rd(),v = rd(),w = rd();add(u,v,w);}
spfa();
cout << (f[n][0]==inf?-1:f[n][0]);
fclose(stdin);
fclose(stdout);
return 0;
}