解题思路
首先可以得到一个很容易得到的贪心策略，将一条路径上最贵的（边权最大）的\(K\)条边删去，那么我们剩下的路径中最贵（边权最大）的路就是原本这条路径上帝\(K + 1\)大的路。
于是原问题就可以转化为：
求一张无向图中最大的一条路径中的第\(K+1\)大的边
这就启发我们枚举所有的路径。
可行吗？
显然是不可行的，这个路很多，但是我们可以反向思考
我们可以假定一个距离\(x\)，然后看看这张图上是否存在一条路径，使它上面第\(K + 1\)大的边长度为\(x\),进一步的，我们可以转化成为在这张图中，是否存在\(K\)条边，任意一条边的权重\(W_{i}>x\)
这样我们的\(check\)函数似乎就呼之欲出了
check函数
这里的\(check\)我们判断一张图中是否有\(K\)条权重大于\(x\)的边，可以进行一下转换：
对于边权\(W_{i} > x\) 的边，设置权重\(w_{i} = 1\)（这是小w，不是原题给定权重）
反之设置权重\(w_{i} = 0\)
然后跑下这张图的最短路(\(从1到N\)),判断是否\(\le k\)即可
Dijkstra写法 \(O(mlog^{2}n)\)
这没什么好说的，就是建图跑最短路，因为边权非负（只能是\(0或1\)）
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 20020;
int h[N], e[N], w[N], ne[N], idx;
int dist[N], st[N], n, m, k;
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}
bool check(int x)
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
priority_queue<PII, vector<PII>, greater<> > heap;
dist[1] = 0, heap.push({dist[1], 1});
while (heap.size())
{
auto t = heap.top().second; heap.pop();
if (st[t]) continue ;
st[t] = true ;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i], W = (w[i] > x);
if (dist[j] > dist[t] + W)
{
dist[j] = dist[t] + W;
heap.push({dist[j], j});
}
}
}
return dist[n] <= k;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
memset(h, -1, sizeof h);
while (m -- )
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w), add(v, u, w);
}
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) r = -1;
printf("%d\n", r);
return 0;
}
双端队列广搜 \(O(mlogn)\)
因为边权只有\(0-1\)，可以用双端队列广搜，时间是线性的，再乘上二分次数，是\(O(mlogn)\)
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 20020;
int h[N], e[N], w[N], ne[N], idx;
int dist[N], st[N], n, m, k;
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}
bool check(int x)
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
deque<int> dq;
dist[1] = 0, dq.push_back(1);
while (dq.size())
{
int t = dq.front(); dq.pop_front();
if (st[t]) continue ;
st[t] = true ;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i], W = (w[i] > x);
if (dist[j] > dist[t] + W)
{
dist[j] = dist[t] + W;
if (W) dq.push_back(j);
else dq.push_front(j);
}
}
}
return dist[n] <= k;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
memset(h, -1, sizeof h);
while (m -- )
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w), add(v, u, w);
}
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) r = -1;
printf("%d\n", r);
return 0;
}
SPFA \(O(mlogn\sim 被卡飞)\)
和Dijkstra一样，跑个最短路
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 20020;
int h[N], e[N], w[N], ne[N], idx;
int dist[N], st[N], n, m, k;
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}
bool check(int x)
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
queue<int> q;
dist[1] = 0, q.push(1), st[1] = true;
while (q.size())
{
int t = q.front(); q.pop();
st[t] = false ;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i], W = (w[i] > x);
if (dist[j] > dist[t] + W)
{
dist[j] = dist[t] + W;
if (!st[j]) q.push(j), st[j] = true ;
}
}
}
return dist[n] <= k;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
memset(h, -1, sizeof h);
while (m -- )
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w), add(v, u, w);
}
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) r = -1;
printf("%d\n", r);
return 0;
}
关于时间
\(AcWing:Dijkstra\ 150ms，双端队列BFS\ \ 56ms，SPFA\ 63ms\)
\(Luogu:Dijkstra\ 238ms, 双端队列BFS\ 73ms， SPFA\ 89ms\)