题目描述

在郊区有 N 座通信基站，P 条 双向 电缆，第 i 条电缆连接基站 Ai 和 Bi。

特别地，1 号基站是通信公司的总站，N 号基站位于一座农场中。

现在，农场主希望对通信线路进行升级，其中升级第 i 条电缆需要花费 Li。

电话公司正在举行优惠活动。

农产主可以指定一条从 1 号基站到 N 号基站的路径，并指定路径上不超过 K 条电缆，由电话公司免费提供升级服务。

农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。

求至少用多少钱可以完成升级。

输入格式

第 1 行：三个整数 N，P，K。

第 2..P+1 行：第 i+1 行包含三个整数 Ai,Bi,Li。

输出格式

包含一个整数表示最少花费。

若 1 号基站与 N 号基站之间不存在路径，则输出 −1。

数据范围

0≤K<N≤1000,
1≤P≤10000,
1≤Li≤1000000

样例

输入样例：

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

输出样例：

4

Dijkstra + 二分

二分性质：

定义在[0 , 1000001]区间中的性质如下：
对于区间中的某一个点，
求出从1走到N，最少经过的长度大于x的边的数量是否小于等于k

Dijkstra思路：

求出从1到N最少经过几条长度大于x的边，
可以将所有边分类：如果边长大于x，则权值看做1，小于x则权值看做0

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int ,int>PII;

const int N = 1010 , M = 200010;

int n , m , k;
int h[N] , e[M] , ne[M] , w[M] , idx;
int dis[N];
bool st[N];

void add(int a , int b , int c)
{
    e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx ++ ;
}

bool dijkstra(int mid)//check
{
    memset(st , false , sizeof st);
    memset(dis , 0x3f , sizeof dis);
    dis[1] = 0;

    priority_queue<PII , vector<PII> , greater<PII>>heap;
    heap.push({0 , 1});

    while(!heap.empty())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second , distance = t.first;
        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver] ; i != -1 ; i = ne[i])
        {
            int j = e[i];
            if(w[i] > mid)//权值大于mid就视为1
            {
                dis[j] = min(dis[j] , distance + 1);
                heap.push({dis[j] , j});
            }
            else//小于x就视为0
            {
                dis[j] = min(dis[j] , distance);
                heap.push({dis[j] , j});
            }
        }
    }

    return dis[n] <= k;
}

int main()
{
    cin >> n >> m >> k;

    memset(h , -1 , sizeof h);

    while(m -- )
    {
        int a , b , c;
        cin >> a >> b >> c;
        add(a , b , c) , add(b , a , c);
    }

    int l = 0 , r = 1e6 + 1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(dijkstra(mid)) r = mid;
        else l = mid + 1;
    }

    if(r == 1e6 + 1) r = -1;

    cout << r << endl;

    return 0;
}