Rt，CSP-J T4。

纯暴力BFS的代码，民间 50pts；官方5pts。

#include <bits/stdc++.h>
using namespace std;
int n,m,k,c,ans=2147483647;
struct edge{int t,o;} tmp;
vector<edge> a[20005];
queue<int> qn;
queue<int> qt;
bool check(int p)
{
	int cnt=0;
	qn.push(1); qt.push(p*k);
	while (!qn.empty())
	{
		int now=qn.front();
		int nt=qt.front();
		for (int i=0; i<a[now].size(); i++)
		{
			if (a[now][i].o<=nt)
			{
				qn.push(a[now][i].t);
				qt.push(nt+1);
			}
		}
		if (now==n && nt%k==0)
		{
			ans=min(ans,nt);
			return 1;
		}
		qn.pop(); qt.pop();
	}
	return 0;
}
int main()
{
	scanf("%d %d %d",&n,&m,&k);
	for (int i=1; i<=m; i++)
	{
		scanf("%d %d %d",&c,&tmp.t,&tmp.o);
		a[c].push_back(tmp);
	}
	int l=1,r=1000000/k,mid;
	while (l<=r)
	{
		mid=(l+r)/2;
		if (check(mid))
		{
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
		while (!qn.empty())
		{
			qn.pop();
			qt.pop();
		}
	}
	if (ans==2147483647)
	{
		cout<<-1;
		return 0; 
	} 
	cout<<ans;
	return 0;
}
/*
5 5 3
1 2 0
2 5 1
1 3 0
3 4 3
4 5 1
*/