J组T4我开始以为暴力 bfs 只能拿 25pts，所以如果 n>10 和 m>15 的都只输出的 -1。

然后呢？100pts->30pts

不特判就一等稳了，现在好了，225pts悬着的。。。

问一下，暴力bfs能给卡掉吗。

代码给上：

//O(?)bao li
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main(){
// 	freopen("bus.in","r",stdin);
// 	freopen("bus.out","w",stdout);
	int n,m,k;
	cin >> n >> m >> k;
   /*
   if (n>10 && m>15){//万恶之源
		cout<<-1<<endl;
		return 0;
	}
  */
	vector<vector<pair<int,int> > > g(n+1);
	vector<vector<int> > g2(n+1);
	int mx=-1;
	for (int i=0;i<m;++i){
		int u,v,a;
		cin >> u >> v >> a;
		g[u].emplace_back(v,a);
		g2[v].emplace_back(u);
		mx=max(mx,a);
	}
	queue<int> qu;
	qu.emplace(n);
	vector<bool> ttflag(n+1,false);
	while (!qu.empty()){
		int he=qu.front();
		if (he==1){
			break;
		}
		qu.pop();
		for (int i=0;i<g2[he].size();++i){
			if (!ttflag[g2[he][i]]){
				ttflag[g2[he][i]]=true;
				qu.emplace(g2[he][i]);
			}
		}
	}
	if (!ttflag[1]){
		cout<<-1<<endl;
		return 0;
	}
	int mn=0x3f3f3f3f;
	for (int qwq=0;qwq<=mx;qwq+=k){
		queue<int> q;
		q.emplace(1);
		int time=qwq;
		while (!q.empty()){
			bool tflag=false;
			vector<bool> flag(n+1,false);
			int len=q.size();
			for (;len!=0;--len){
				int t=q.front();
				q.pop();
				if (t==n && time%k==0){
					tflag=true;
					break;
				}
				for (int i=0;i<g[t].size();++i){
					pair<int,int> item=g[t][i];
					if (item.second<=time && !flag[item.first]){
						flag[item.first]=true;
						q.emplace(item.first);
					}
				}
			}
			if (tflag){
				mn=min(mn,time);
				break;
			}
			++time;
		}
	}
	if (mn==0x3f3f3f3f){
		cout<<-1<<endl;
	}else{
		cout<<mn<<endl;
	}
// 	fclose(stdin);
// 	fclose(stdout);
	return 0;
}