专注 效率 记忆
预习 笔记 复习 做题

欢迎观看我的博客，如有问题交流，欢迎评论区留言，一定尽快回复！（大家可以去看我的专栏，是所有文章的目录）
　
文章字体风格：
红色文字表示：重难点★✔
蓝色文字表示：思路以及想法★✔
　
如果大家觉得有帮助的话，感谢大家帮忙
点赞！收藏！转发！

截取重要部分，看完全篇即懂
利用二分遍历最终答案
也就是遍历
第k+1条边的最小值
每次二分一个值
然后让图中所有大于该值的边为1
所有小于该值的边 为0
然后从起到走到终点
看最小距离（也就是大于该值的边数）
如果边数大于K了，那么以该值为最终答案，一定会使得最终答案变小，所以左区间右移（下次遍历更大的值）
如果边数等于K，那么该值为最终答案或许合适（右区间左移，下次遍历更小的值）
如果边数小于K，那么该值可能使得最终答案变大（也就是大于最终答案）那么也右区间左移动（下次遍历更小的值）

本题题意：
起点到终点 走哪条路径使得（路径长度排序后从大到小） 第k+1条边最小

一种想法就是
遍历所有
起点到终点的路径
求出第k+1边

这样时间复杂度太大

优化：
二分

利用二分遍历最终答案

也就是遍历
第k+1条边的最小值

每次二分一个值

然后让图中所有大于该值的边为1
所有小于该值的边 为0

然后从起到走到终点

看最小距离（也就是大于该值的边数）

如果边数大于K了，那么以该值为最终答案，一定会使得最终答案变小，所以左区间右移（下次遍历更大的值）

如果边数等于K，那么该值为最终答案或许合适（右区间左移，下次遍历更小的值）

如果边数小于K，那么该值可能使得最终答案变大（也就是大于最终答案）那么也右区间左移动（下次遍历更小的值）

补充问题：0 1边权，求最小距离

可以用双端队列
双端队列求最小距离

#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>using namespace std;const int N = 1010, M = 20010;int n, m, k;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
deque<int> q;
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 check(int bound)
{memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);q.push_back(1);dist[1] = 0;while (q.size()){int t = q.front();q.pop_front();if (st[t]) continue;st[t] = true;for (int i = h[t]; ~i; i = ne[i]){int j = e[i], x = w[i] > bound;if (dist[j] > dist[t] + x){dist[j] = dist[t] + x;if (!x) q.push_front(j);else q.push_back(j);}}}return dist[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 (check(mid)) r = mid;else l = mid + 1;}if (r == 1e6 + 1) cout << -1 << endl;else cout << r << endl;return 0;
}