# hihoCoder 1139-二分·二分答案

hihoCoder 1139-二分·二分答案

#1139 : 二分·二分答案

5 6 2 5
1 2 3
1 3 2
1 4 4
2 5 2
3 5 5
4 5 3

3

f(x)可以使用广度优先搜索实现。实现的时候注意不能使用邻接矩阵保存图，有可能TLE或MLE，使用邻接表更好。完整代码如下：

```#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int kMaxN = 10005, kINF = 0x3f, kMaxW = 1000005;
vector<vector<int>> path;
vector<vector<int>> powers;
vector<bool> visit;
int n, m, k, t;

bool BFS(int power)
{
visit.clear();
visit.resize(n + 1, false);
queue<int> Q;
int u, v, len = 0;;
Q.push(1);
visit[1] = true;
Q.push(-1);
while (!Q.empty()&&len<k)
{
u = Q.front();
Q.pop();

if (u == -1)
{
if (Q.empty())
return false;
else
{
len++;
Q.push(-1);
continue;
}
}
for (int i = 0; i < path[u].size(); i++)
{
v = path[u][i];
if (!visit[v]&&powers[u][i] <= power)
{
if (v == t)
return true;
visit[v] = true;
Q.push(v);
}
}
}
return false;
}
int main()
{
freopen("input.txt", "r", stdin);

scanf("%d %d %d %d", &n, &m, &k, &t);
path.resize(n + 1);
powers.resize(n + 1);

int u, v, w, low = kMaxW, high = 0;
for (int i = 0; i < m; i++)
{
scanf("%d %d %d", &u, &v, &w);
low = min(low, w);
high = max(high, w);
path[u].push_back(v);
path[v].push_back(u);
powers[u].push_back(w);
powers[v].push_back(w);
}
while (low+1 < high)
{
int mid = (low + high) / 2;
if (BFS(mid))
high = mid;
else
low = mid;
}
printf("%d\n", high);
return 0;
}
```