【算法】通信线路（二分，堆优化版dijkstra）

算法】通信线路（二分，堆优化版dijkstra）"/>

【算法】通信线路（二分，堆优化版dijkstra）

题目

        在郊区有 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

暴力写法，我们可以从0遍历到1000001，找到一个值x：

        1、在选择 1 ~  n 的路线中，比这个值x大的边权为 k 个。

        2、在满足1条件的 x 集合中，选取最小的那个值。

在寻找最短路的时候，可以将大于 x 的边权当作 1 ，把小于等于 x 的边权当作 0 。

dist数组中储存到当前点经过的大于x的边的个数。

从0~1000001时间复杂度太大，可以使用二分进行优化。

代码 

#include<bits/stdc++.h>
using namespace std;const int N = 1010,M = 20010;
typedef pair<int,int> PII;
int n,m,k;// n点数，m边数，k免费电缆数
int h[N],e[M],w[M],ne[M],idx;// 加权邻接表五件套
int dist[N];// 到达第i的点，最少经过多少个超过bound的电缆
bool st[N];// 第i个点的最小值是否已经被确定void add(int a,int b,int c)
{e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}bool check(int bound)// 堆优化版dijkstra算法
{memset(st,0,sizeof(st));// 初始状态，所有点都没有确定最小值memset(dist,0x3f,sizeof(dist));// 所有点的距离初始为无穷大dist[1] = 0;// 通信公司的总站为0priority_queue<PII,vector<PII>,greater<PII>> q;q.emplace(0,1);st[1] = true;while(!q.empty()){auto t = q.top();// 取出队头节点，此时该点已经确定为最小值q.pop();int x = t.second;st[x] = false;for(int i = h[x]; i != -1; i = ne[i]){int j = e[i],v = w[i] > bound;// 如果这条边的边权大于bound，则边权为1if(dist[j] > dist[x] + v){dist[j] = dist[x] + v;if(!st[j]){st[j] = true;q.emplace(dist[j],j);}}}}return dist[n] <= k;
}int main()
{cin >> n >> m >> k;// n点数，m边数，k免费电缆数memset(h,-1,sizeof(h));// 将表头初始化为-1while(m --)// 输入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) / 2;if(check(mid)) r = mid;else l = mid + 1;}if(l == 1e6 + 1) l = -1;cout << l << endl;return 0;
}