https://www.luogu.com.cn/problem/P9751 弄了半天样例都过不了...

#include <bits/stdc++.h>
using namespace std;

const int N = 400010;
int n,m,k;
int h[N],e[N],ne[N],w[N],idx;
int a[N],dist[N];
bool vis[N];
void add(int a,int b,int c)
{
	w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool check(int d)
{
	queue<int> q;
	dist[n]=d;
	q.push(n);
	while(!q.empty())
	{
		
		int f=q.front();
		q.pop();
		for(int i=h[f];i!=-1;i=ne[i])
		{
			if(dist[f]-1>=w[i] && !vis[e[i]])
			{
				dist[e[i]]=dist[f]-1;
				vis[e[i]]=1;
				q.push(e[i]);
			}
		}
	}
	if(dist[1]>=0) return true;
	return false;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);memset(h,-1,sizeof h);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(b,a,c);
	}
	int l=1,r=n,best=-1;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(mid*k)) best=mid,l=mid+1;
		else r=mid-1;
		for(int i=1;i<=n;i++) dist[i]=0;
	}
	if(best==-1) printf("-1");
	else printf("%d",best*k);
}