题目分析

• 题目要求为 “农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。求至少用多少钱可以完成升级。” 可知这是一个“最小化最大值”的问题，这种问题往往可以用二分查找来解决，因为我们可以通过猜测一个“最大值”并验证其可行性，逐步逼近最优解。
• 有N个节点和P条边，需要从1到N连通，明显是图论问题。我们需要在图上找到一条路径，满足某种条件（免费电缆数≤K），这提示我们需要一个路径搜索算法。
• 对于一个给定的“最大长度–mid”，我们需要判断是否能用≤K根免费电缆连通1到N。这是一个“yes/no”问题.

推导解题思路

第一步：明确目标

• 目标是找到一个最小的值X，使得：
• 所有长度≤X的电缆由农民付费。
• 长度>X的电缆用免费电缆覆盖，且数量≤K。
• 1到N仍然连通。
• 这个X就是“需要支付的电缆的最大长度”，我们要最小化它。

第二步：识别“最小化最大值”

• “最小化某个最大值”是二分查找的经典应用场景。
• 我们可以二分枚举X的值（范围在0到10^6，因为电缆花费上限是10^6），然后检查每个X是否可行。
• 可行性检查：给定X，能否用≤K根免费电缆覆盖所有>X的边，同时连通1到N？

第三步：建模为图问题

• 杆子是节点，电缆是边，构成了一个无向图。
• 对于某个X：
• 长度≤X的边不需要免费电缆（付费），此时边权为0。
• 长度>X的边需要1根免费电缆,此时边权为1。
• 我们需要在图上找到一条从1到N的路径，使得路径上长度>X的边数≤K。

第四步：选择路径算法

• 这是一个单源路径问题（从1到N）。
• “距离”定义为“长度>X的边数”，需要找到最优路径（即所需免费电缆最少）。
• 这里可以用最短路径算法，但需要适配特殊距离定义：
• Dijkstra：适合正权图，但这里的“距离”（0或1）不完全符合传统加和规则。
• Bellman-Ford：可以处理，但复杂度O(VE)太高。
• SPFA：队列优化版Bellman-Ford，平均复杂度O(E)，能灵活处理自定义距离，适合稀疏图（P≤10000）。

第五步：联合二分与SPFA

• 二分查找猜测X（即mid）。
• SPFA验证：计算从1到N的最少免费电缆数（dist[n]），检查是否≤K。
• 结合起来：二分+SPFA就能高效解决问题。

代码

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;
int n, p, k;
vector<vector<pair<int, int>>> adj;
//邻接矩阵  adj[i] = {j, l} 表示 i与j相连，花费为l

bool check(int mid){
    vector<int> dist(n + 1, INF);
    vector<bool> in_queue(n + 1, false);
    queue<int> q;

    dist[1] = 0;
    q.push(1);
    in_queue[1] = true;

    while(!q.empty()){
        int curr = q.front();
        q.pop();
        in_queue[curr] = false;

        for(auto item : adj[curr]){//遍历所有与curr相邻的点
            int next = item.first;
            int len = item.second;
            int new_dist = dist[curr] + (len > mid ? 1 : 0);
            //特殊的边权，如果len<mid表示不需要花费的额度

            if(new_dist < dist[next]){
                dist[next] = new_dist;
                if(!in_queue[next]){
                    q.push(next);
                    in_queue[next] = true;
                }
            }
        }
    }

    return dist[n] <= k;
    //dist数组记录的是，需要免费的电缆的根数，如果根数>k说明检查不通过
}

int main(){
    cin >> n >> p >>k;
    adj.resize(n + 1);

    //建图 
    for(int i = 0; i < p; i ++ ){
        int a, b, l;
        cin >> a >> b >> l;
        adj[a].push_back({b, l});
        adj[b].push_back({a, l});
    }

    int left = 0, right = 1000000;
    int ans = -1;

    while(left <= right){
    //这样的二分会得到一个较小值
    //具备单调性，如果mid = x通过check，表示任何>x的值都会通过检查
    //因为我们想要的是最小值，所以r = mid - 1;
        int mid = left + right +1 >> 1;
        if(check(mid)){
            ans = mid;
            right = mid - 1;
        }
        else left = mid + 1;
    } 

    cout << ans << endl;
    return 0;
}