提交记录https://www.luogu.com.cn/record/131206839

code

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

const int maxn=1e4+1;
int n,m,k;
int vis[maxn];
vector<pair<int,int>>v[maxn];
queue<pair<int,int>>q;

void bfs()
{
	memset(vis,0x3f,sizeof(vis));
	q.push({1,k});
	while(!q.empty())
	{
		int now=q.front().first,t=q.front().second;
		q.pop();
		if(vis[now]<=t)
		{
			continue;
		}
		vis[now]=t;
		for(pair<int,int>i:v[now])
		{
			q.push({i.first,max(i.second,t+1)});
		}
	}
}

signed main()
{
//	freopen("bus.in","r",stdin);
//	freopen("bus.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		int u,b,a;
		cin>>u>>b>>a;
		v[u].push_back({b,a});
	}
	bfs();
	if(vis[n]%k!=0)
	{
		vis[n]/=k;
		vis[n]*=k;
		vis[n]+=k;
	}
	cout<<vis[n]<<endl;
	return 0;
}