题目链接：http://hihocoder.com/contest/hiho38/problem/1 ，挺难想的解题思路，好题。
按照提示的算法来：
我们需要找什么？
在这个题目中我们需要找的是路径最长边。比如存在一条路径{1, p[1], p[2], ... , p[j], T}, p = {p[1],p[2],...,p[j]] }， j < K，我们需要找的为 D(P) = Max{w(1, p[1]), w(p[j], T), Max{w(p[i], p[i+1]) | 1 <= i < j} }。则这道题的结果为找出所有从1到T的路径P'，求的Min{D(P')}。由于给定的图存在环，所以要枚举出所有1到T的路径是很难的，因此我们需要换个角度去思考这个问题。
这道题结果有什么特殊性？
不妨假设答案为j，如果舰队满足j以上的索敌值，那么一定存在至少一条路径可以从1到T，并且路径数量小于K。如果舰队索敌值小于j，则在K条路径的条件下一定无法从1到T。否则j就不是最小值了。
则对于索敌值满足这样一个关系：
可以看出，j值刚好是是否存在路径的一个分界线。如果我们枚举一个j'：
j'<j，无法到达boss点
j'>=j，一定可以到达boss点
则如何快速的找到这个分界线j，就是解决这道题目的关键。
不妨设f(x) = true(索敌值为x时，可以达到boss点), false(索敌值为x时，不能达到boss点)
二分枚举，设定枚举区间[L,R]，满足f(L)=false, f(R)=true。每次取中间值Mid=(L+R)/2，若f(Mid)=true，令R=Mid；否则令L=Mid。
当L+1=R时，可以知道R即为我们需要寻找的j。
关于f(x)的求法：
可以用BFS来判断，这里要用一个数组deep[]记录每个结点的深度信息。所以访问到一个结点时，判断该结点是否能加入队列的条件有三个：该点未访问；到达该点后路径长度不超过k(用deep[]数组来判断)；当前的索敌值x不小于这条边的索敌值w。
如果能在限制条件下到达boss的位置就返回true，否则返回false。
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL __int64
#define eps 1e-8
#define INF 1000005
const int maxn = + ;
struct Edge {
int v , w;
};
vector <Edge> e[maxn]; //邻接表来表示图
int vis[maxn] , deep[maxn];
bool check(int start , int j , int k , int end)
{ //用BFS来判断，起始点为start，j为最小索敌值，k为限制路径长度
memset(vis , , sizeof(vis));
queue <int> que;
que.push(start);
vis[start] = ;
deep[start] = ;
while(!que.empty()) {
int u = que.front();
que.pop();
for(int i = ; i < e[u].size() ; i++) {
int v = e[u][i].v;
int w = e[u][i].w;
if(!vis[v] && deep[u] < k && j >= w) { //三个条件
if(v == end)
return true;
vis[v] = ;
deep[v] = deep[u] + ;
que.push(v);
}
}
}
return false;
}
int binary_search(int l , int r , int k , int t)
{ //二分答案，区间为[l , r]，限制路径长度k，终点为t
int m = (l + r) >> ;
while(l + != r) {
if(check( , m , k , t))
r = m;
else
l = m;
m = (l + r) >> ;
}
return r;
}
int main()
{
int n , m , k , t;
scanf("%d %d %d %d" , &n , &m , &k , &t);
while(m--) {
int u , v , w;
scanf("%d %d %d" , &u , &v , &w);
Edge tmp = {v , w};
e[u].push_back(tmp);
tmp.v = u;
e[v].push_back(tmp);
}
int res = binary_search( , INF , k , t);
printf("%d\n" , res);
return ;
}