正文
POJ 3662 Telephone Lines (二分+Dijkstra: 最小化第k大的值)
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题意
Farmer John想从电话公司修一些电缆连接到他农场。已知N个电线杆编号为1,2,⋯N，其中1号已经连接电话公司，N号为农场，有P对电线杆可连接。
现给出P对电线杆距离Ai,Bi,Li表示Ai和Bi可连接，需要长度为Li的电缆。
电话公司赞助FJ K条免费电缆，额外的支出为剩下所需电缆的 最大长度 。求出最小费用。
思路
设mid为某条线的长度，长于mid的线放到免费额度里，否则自己掏钱。如果存在一个临界值x，使得长于x的电线数量恰好等于K，这个临界值对应的解就是最优解。如何计算长于mid的电线数量呢？排序比较肯定不行的，因为不知道这条电线用不用得上。所以需要Dijkstra，又因为在mid固定的条件下，电线的花费只取决于长度是否大于mid，所以可以将大于的取为1，小于的取为0。这样花费就可以计算了，并且花费等于长于mid的电线数量，也就是需要自己掏钱的电线的数量。
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int N, P, K;
struct edge { // 顶点属性
int to, length;
edge(int to, int length) : to(to), length(length) {}
bool operator<(const edge &b) const {
return length > b.length;
}
};
vector<edge> G[1005];
int d[1005];
bool dijkstra_C(int s, int x) { // 求出长度>x的最少个数（>x边权为1，否则为0，求最短路），判断x是否免费，当二分判定出第一个不免费的x，就是所求的最小的最大x。
priority_queue<edge> que;
memset(d, 0x3f, sizeof(d));
d[s] = 0;
que.push(edge(s, 0));
while (!que.empty()) {
edge p = que.top(); que.pop();
int v = p.to;
if (d[v] < p.length) continue;
for (unsigned int i = 0; i<G[v].size(); ++i) {
edge e = G[v][i];
int len = e.length > x;
if (d[e.to] > d[v] + len) {
d[e.to] = d[v] + len;
que.push(edge(e.to, d[e.to]));
}
}
}
return d[N] <= K;
}
void solve() {
dijkstra_C(1, 1);
if (d[N] == 0x3f3f3f3f) {
printf("-1\n");
return;
}
int lb = -1, ub = 1000000 + 5; // (lb, ub)
while (ub - lb > 1) {
int mid = (lb + ub) >> 1;
if (dijkstra_C(1, mid)) ub = mid; // (lb, ub]
else lb = mid;
}
printf("%d\n", ub);
}
int main() {
scanf("%d%d%d", &N, &P, &K);
int a, b, l;
for (int i = 0; i < P; ++i) {
scanf("%d%d%d", &a, &b, &l);
G[a].push_back(edge(b, l));
G[b].push_back(edge(a, l));
}
solve();
return 0;
}
