RT。思路是二分到达时间+bfs 跑分层图最短路。悬关qwq

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=1e4+5;
long long n,m,k;
vector<pii>G[N];
int dis[N][105];
bool ok(int x)
{
	memset(dis,0x3f,sizeof(dis)),dis[1][0]=x;
	queue<pii>q;
	q.push({1,0});
	while(!q.empty())
	{
		int u=q.front().first,r=q.front().second,d=dis[u][r];
		q.pop();
		for(pii i:G[u])
		{
			int v=i.first,w=i.second;
			if(d>=w&&dis[v][(r+1)%k]>d+1)
			{
				dis[v][(r+1)%k]=d+1;
				q.push({v,(r+1)%k});
			}
		}
	}
	return dis[n][0]!=dis[0][0];
}
signed main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		G[x].push_back({y,z});
	}
	int l=-1,r=1e6/k+1;
	while(l+1<r)
	{
		int mid=(l+r)>>1;
		if(ok(mid*k))r=mid;
		else l=mid;
	}
	ok(r*k);
	if(dis[n][0]!=dis[0][0])cout<<dis[n][0];
	else cout<<"-1";
	return 0;
}