题目
给定N个点和M条边，从点1出发，到达点T。寻找路径上边的个数小于等于K的路径，求出所有满足条件的路径中最长边长度的最小值。
题目链接:二分
最小化最大值，考虑采用二分搜索。对所有的边长进行排序，二分，对每次选择的边长，判断是否存在一条路径满足路径上所有的边长度均小于等于该边长，且路径中的边的个数小于等于K。
在判断路径是否存在的时候，使用BFS搜索，因为BFS用于寻找最短（边的个数最少）路径。
实现
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
using namespace std;
struct Edge{int to;int dist;int next;
};
//边的个数，开始的时候数组开的长度为 100005， hihocoder上提示 TLE，实际应该为 RE！！！
//数组开到 200005，就AC了
Edge gEdges[200005];
int gHead[10005];
bool gVisited[10005];
int gEdgeIndex;
void Init(){gEdgeIndex = 0;memset(gEdges, -1, sizeof(gEdges));memset(gHead, -1, sizeof(gHead));memset(gVisited, false, sizeof(gVisited));
}
void InsertEdge(int u, int v, int d){int e = gEdgeIndex++;gEdges[e].to = v;gEdges[e].dist = d;gEdges[e].next = gHead[u];gHead[u] = e;
}
struct Node{int id;int step;Node(int i = 0, int s = 0) :id(i), step(s){};
};
//BFS 搜索，寻找从点1到达点boss的路径，要求路径上的所有边的长度都小于等于max_d，且路径长度最大为k
//判断能否找到满足要求的路径
bool Arrive2Boss(int boss, int max_d, int k){queue<Node> Q;Node node(1, 1);Q.push(node);memset(gVisited, false, sizeof(gVisited));while (!Q.empty()){node = Q.front();Q.pop();if (node.id == boss)return true;if (gVisited[node.id])continue;gVisited[node.id] = true;for (int e = gHead[node.id]; e != -1; e = gEdges[e].next){int v = gEdges[e].to;if (!gVisited[v] && gEdges[e].dist <= max_d && node.step <= k){Q.push(Node(v, node.step + 1));}}}return false;
}
int edges_len[100005];
int main(){int N, M, K, T, u, v, d;Init();scanf("%d %d %d %d", &N, &M, &K, &T);for (int i = 0; i < M; i++){scanf("%d %d %d", &u, &v, &d);InsertEdge(u, v, d);InsertEdge(v, u, d);edges_len[i] = d;}//对路径进行排序sort(edges_len, edges_len + M);int beg = 0, end = M;//二分查找while (beg < end){int mid = (beg + end) / 2;int max_d = edges_len[mid];if (Arrive2Boss(T, max_d, K)){end = mid;}elsebeg = mid + 1;}int result = edges_len[beg];printf("%d\n", result);return 0;
}
