POJ 3662 Telephone Lines 二分，最小化第k大的数

一、题目大意

我们有n个点，p条边，最小化从1到n之间的路径的第k+1大的数（当路径不超过k时就是0）

二、解题思路

我们首先用dijkstra过一遍，判断从1能不能到n，不能直接输出-1结束。

1能到达n的话，就对二分第k+1大的边进行二分，left选-1，right选最大的边的长度+1（这里我left一开始选取的时最小边-1，后来发现当k比较大时结果可能是0）

二分的依据如下

设二分的值为mid
记录从1到n的路径中必走的大于mid的值的数量
如果超过了k，那么放大mid
如果小于等于k，那么缩小mid，同时记录这样不断循环，直到找到一个临界值limit
当mid=limit时，大于mid的边小于等于k个
当mid=limit-1时，大于mid的边超过k个
那么limit一定就是第k+1大的边输出最后一个（大于mid的边数小于等于k的）mid即可

三、代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> P;
vector<P> edges[1007];
bool used[1007];
int n, p, k, d[1007], inf = 0x3f3f3f3f, maxt = 0;
void input()
{int from, to, cost;scanf("%d%d%d", &n, &p, &k);for (int i = 0; i < p; i++){scanf("%d%d%d", &from, &to, &cost);edges[from - 1].push_back(P(cost, to - 1));edges[to - 1].push_back(P(cost, from - 1));maxt = max(cost, maxt);}
}
bool judgeByDijkstra(int mid)
{for (int i = 0; i < n; i++){d[i] = inf;used[i] = false;}d[0] = 0;priority_queue<P, vector<P>, greater<P>> que;que.push(P(d[0], 0));while (!que.empty()){P current = que.top();que.pop();if (used[current.second] || current.first > d[current.second]){continue;}used[current.second] = true;for (int i = 0; i < edges[current.second].size(); i++){P toEdge = edges[current.second][i];int relativeEdge = toEdge.first > mid ? 1 : 0;if (d[current.second] + relativeEdge < d[toEdge.second]){d[toEdge.second] = d[current.second] + relativeEdge;que.push(P(d[toEdge.second], toEdge.second));}}}return d[n - 1] <= k;
}
void binarySearch()
{int left = -1, right = maxt + 1;while (left + 1 < right){int mid = (left + right) / 2;if (judgeByDijkstra(mid)){right = mid;}else{left = mid;}}printf("%d\n", right);
}
bool judgeIfCanGet()
{for (int i = 0; i < n; i++){d[i] = inf;used[i] = false;}d[0] = 0;priority_queue<P, vector<P>, greater<P>> que;que.push(P(d[0], 0));while (!que.empty()){P current = que.top();que.pop();if (used[current.second] || current.first > d[current.second]){continue;}used[current.second] = true;for (int i = 0; i < edges[current.second].size(); i++){P toEdge = edges[current.second][i];if (d[current.second] + toEdge.first < d[toEdge.second]){d[toEdge.second] = d[current.second] + toEdge.first;que.push(P(d[toEdge.second], toEdge.second));}}}return d[n - 1] != inf;
}
int main()
{input();if (!judgeIfCanGet()){printf("-1\n");}else{binarySearch();}return 0;
}