题目描述

blablabla

样例

blablabla

算法1

(二分答案) $O((N+P)logMAX_L))$

首先答案是单调的的, 显然我们想让第K+1大的边最小,答案是单调的
再看一眼范围, N和P很小, L很大, 有了二分的可能

那怎么check 呢?

我们就是为了让存在 mid K条边比 mid 大
那为何不让 比 mid 大的边的权值直接为 1, 小与等于的为 0
这不就成了 01 单源最短路了吗, 直接 用双端队列做

对于为什么 等于 mid 的也为零, 因为我的二分是 l < r(如果你的不是,你要自己判断相等情况) 只要让 l = mid ,
那么 对于这个 mid 情况还在 l~r 的区间内为备选答案, 由于只要存在通路答案必然存在的特性
如果 这个mid 是答案, 最后的二分必将趋向mid l= r = mid

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>
#define pb emplace_back
#define pf emplace_front
#define fi first
#define se second
using namespace std;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int maxn = 10005;

int n, m, k, mx, v[1005];
vector<PII> h[1005];

int check(int m, int c)
{
    deque<PII> q;
    q.pb(PII{1, 0});
    while (!q.empty())
    {
        PII p = q.front();
        if (p.fi == n)  return k >= p.se;
        q.pop_front();
        if (v[p.fi] == c) continue;
        v[p.fi] = c;
        for (PII i : h[p.fi])
            if (i.se > m) q.pb(PII{i.fi, p.se + 1});
            else q.pf(PII{i.fi, p.se});
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1, u, v, co; i <= m; ++i)
    {
        cin >> u >> v >> co;
        h[u].pb(PII{v, co}); h[v].pb(PII{u, co});
        mx = max(mx, co);
    }
    int l = 0, r = mx, ans, c = 0;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        ans = check(mid, ++c);
        if (ans == - 1) break;
        if (ans == 1) r = mid;
        else l = mid + 1;
    }
    if (ans == -1) {cout << -1; return 0; }
    cout << l;
    return 0;
}