题目链接:https://www.luogu.com.cn/problem/P1948
题意： n个点，p条边，政府可以给免费修k条路，问你找到一条从1号点到n号点的最短路径长度，而这条最短路的代价是这条路径上的花费最大的价钱（除去至多k条最大的价钱之后） 下面是这个题中最重要的信息： 电信公司决定支援灾区免费为此市连接k对由笨笨指定的电话线杆，对于此外的那些电话线，需要为它们付费，总费用决定于其中最长的电话线的长度(每根电话线仅连接一对电话线杆)。如果需要连接的电话线杆不超过k对，那么支出为0.
题解： 首先这个题让求的总费用是最长的电话线的长度 假设答案是ans，那么答案肯定是在0到最大花费+1之间，其实答案应该是在0到最大花费之间，而我这里说在0到最大花费+1，是为了如果答案是最大花费+1，那么这个答案就是-1，也就是题目中的不可能完成； 接着我们考虑0 <= ans <= maxval; 下面我们就对这个区间进行二分，mid = l + r； 如果mid符合的话，那么肯定可以找到一条路，这条路上的大于mid的个数肯定是小于等于k的（答案就在l 到mid之间），否则mid就是不符合，那么答案肯定是在mid + 1 到 r之间；
#include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std; const int N = 1010; vector<pair<int,int>>v[N]; // 建立邻接表 int n,m,k; bool st[N]; // dijkstra bool check(int cost) { memset(st,0,sizeof st); priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q; q.push({0,1}); while(q.size()) { auto t = q.top();q.pop(); int dis = t.first; int p = t.second; st[p] = true; for(auto &x : v[p]) { // 如果当前的边权大于我们的答案，那么这条边就让政府来修 if(x.second > cost){ // 如果政府能修的路还没达到k条，那么就让他修 if(t.first + 1 <= k && !st[x.first]){ // 如果找到了终点，那么一定要提前返回，通过出队来判断终点的话会超时 if(x.first == n){ return true; } q.push({t.first + 1,x.first}); } }else{ // 如果当前的边权不大于我们的答案，那么这条边就可以直接走，对我们的答案并不产生影响 if(!st[x.first]){ if(x.first == n){ return true; } q.push({t.first,x.first}); } } } } return false; } int main() { // 输入n,m,k scanf("%d%d%d",&n,&m,&k); int l = 0,r = 0; // 左边界l，右边界r for(int i = 0;i < m;i ++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); v[a].push_back({b,c}); v[b].push_back({a,c}); r = max(r,c); } int kkk = r + 1; r ++; // 二分 while(l < r) { int mid = l + r>> 1; if(check(mid)){ r = mid; }else{ l = mid + 1; } } if(r == kkk){ printf("%d\n",-1); } else printf("%d\n",r); return 0; }