在上一回和上上回里我们知道Nettle在玩《艦これ》，Nettle在整理好舰队之后终于准备出海捞船和敌军交战了。
在这个游戏里面，海域是N个战略点(编号1..N)组成，如下图所示 ×
提示：你在找什么？
我们需要找什么？
在这个题目中我们需要找的是路径最长边。比如存在一条路径{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，无法到达boss点
-
j'>=j，一定可以到达boss点
输入
第1行：4个整数N,M,K,T。N表示战略点数量，M表示航线数量，K表示最多能经过的航路，T表示boss点编号, 1≤N,K≤10,000, N≤M≤100,000
第2..M+1行：3个整数u,v,w，表示战略点u,v之间存在航路，w表示该航路需求的索敌值，1≤w≤1,000,000。输出
第1行：一个整数，表示舰队需要的最小索敌值。
Sample Input
5 6 2 51 2 31 3 21 4 42 5 23 5 54 5 3
Sample Output
3 这题本菜鸟不看题解根本想不到用二分（也许这就是菜鸟吧）
输入
第1行：4个整数N,M,K,T。N表示战略点数量，M表示航线数量，K表示最多能经过的航路，T表示boss点编号, 1≤N,K≤10,000, N≤M≤100,000
第2..M+1行：3个整数u,v,w，表示战略点u,v之间存在航路，w表示该航路需求的索敌值，1≤w≤1,000,000。输出
第1行：一个整数，表示舰队需要的最小索敌值。
建立一个vector的二维数组里面存储node
qu[a][i].x 表示含义为a岛到i岛所需的索敌值
有了vector的帮助这题就很容易了。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 struct node 8 { 9 int x,y;10 };11 int n,m,k,t;12 vector qu[10010];13 int vis[10010];14 int bfs(int dis)15 {16 memset(vis,0,sizeof(vis));17 queue q;18 q.push(1);19 while(!q.empty()){20 int cur=q.front();21 q.pop();22 if (cur==t) return 1;23 if (vis[cur]==k) continue;24 int len=qu[cur].size();25 for (int i=0 ;i dis) continue;28 vis[temp]=vis[cur]+1;29 q.push(temp);30 }31 }32 return 0;33 }34 int main() {35 while(scanf("%d%d%d%d",&n,&m,&k,&t)!=EOF){36 int a,b,c,maxn=0;37 for (int i=0 ;i