poj 3662 Telephone Lines

Telephone Lines

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 6633		Accepted: 2440

Description

Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system.

There are N (1 ≤ N ≤ 1,000) forlorn telephone poles conveniently numbered 1..N that are scattered around Farmer John's property; no cables connect any them. A total of P (1 ≤ P ≤ 10,000) pairs of poles can be connected by a cable; the rest are too far apart.

The i-th cable can connect the two distinct poles A_i and B_i, with length L_i (1 ≤ L_i ≤ 1,000,000) units if used. The input data set never names any {A_i, B_i} pair more than once. Pole 1 is already connected to the phone system, and pole N is at the farm. Poles 1 and N need to be connected by a path of cables; the rest of the poles might be used or might not be used.

As it turns out, the phone company is willing to provide Farmer John with K (0 ≤ K < N) lengths of cable for free. Beyond that he will have to pay a price equal to the length of the longest remaining cable he requires (each pair of poles is connected with a separate cable), or 0 if he does not need any additional cables.

Determine the minimum amount that Farmer John must pay.

Input

* Line 1: Three space-separated integers: N, P, and K
* Lines 2..P+1: Line i+1 contains the three space-separated integers: A_i, B_i, and L_i

Output

* Line 1: A single integer, the minimum amount Farmer John can pay. If it is impossible to connect the farm to the phone company, print -1.

Sample Input

Sample Output

4



题意：一共有N个电线杆，有P对电线杆是可以连接的，用几条线连接在一起的电线杆之间都可相互通信，现在想要使得电线杆1和电线杆N能相互通信，并且电线公司提出K条电线是可以免费使用的，当使用电线的数量
超过K条，超出的电线要收费，收的总费用为去掉免费使用的K条电线之后最长的那条电线的长度。现在需要尽可能的减少费用，问最少费用是多少。




解题思路：可以二分搜索出所需费用，这样，对于每一个最小费用‘候选人’，都要进行判定是否符合题目条件，换句话说，如果以此为最少所需费用，那么至少需要多少条免费使用的电线，这个值与K进行比较，如果比K大，
说明以此为最少所需费用的话还偏小，搜索范围的下界改为当前的费用‘候选人’，反之改上界。在判断至少需要多少条免费使用的电线时，可以使用dijkstra算法，此时点与点之间的距离大于等于‘候选人’时，需要免费使用
的电线数量要加1，否则不用加。

AC代码：

#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
const int V_MAX = 1000 + 4,L_MAX= 1000000;
struct edge {
    int to, cost;
    edge() {};
    edge(int to, int cost):to(to),cost(cost) {}
};
typedef pair<int, int>P;
int N,E,K;
vector<edge>G[V_MAX];
int d[V_MAX];//储存从起始点到当前点需要免费的道路数量
int dijkstra(int s,int x) {
    priority_queue<P, vector<P>, greater<P>>que;
    fill(d,d+N,INT_MAX);
    d[s] = 0;
    que.push(P(0,s));
    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if (d[v] < p.first)continue;
        for (int i = 0; i < G[v].size(); i++) {
            edge e = G[v][i];
            int new_d = d[v]+(e.cost>=x?1:0);////////////
            if (d[e.to] > new_d) {/////////////
                d[e.to] = new_d;
                que.push(P(d[e.to], e.to));
            }
        }
    }
    return d[N - 1];
}
int main() {
    scanf("%d%d%d",&N,&E,&K);
    for (int i = 0; i < E; i++) {
        int from, to, cost;
        scanf("%d%d%d",&from,&to,&cost);
        from--, to--;
        G[from].push_back(edge(to,cost));
        G[to].push_back(edge(from, cost));
    }

    int lb = 0,ub=L_MAX+2;
    while (ub - lb > 1) {
        int mid = (lb + ub) >> 1;
        if (dijkstra(0, mid) > K)//大于K是因为把自己也算上去了，取值区间[lb,ub)
            lb = mid;//可能mid取太小，还可以大点
        else ub = mid;
    }
    if (lb > L_MAX)lb = -1;
    printf("%d
",lb);
    return 0;
}