题目
给定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;
}
else
beg = mid + 1;
}
int result = edges_len[beg];
printf("%d\n", result);
return 0;
}