原题链接

获取题意

1.只能传送一次。

2.走树边没有限制。

3.只能传送至非相邻节点

4.路径一定是如下形式：

• \(S\to x \to T\) 其中要么 \(x\to T\) 传送要么 \(S\to x\) 传送

• \(S\to x \to y \to T\) 其中 \(x\to y\) 传送

• \(S\to T\) 要么直接传送，要么全程走树边

分析

我们发现，如果传送，那么每一组传送对应的最短路径是唯一的。

因此，我们可以遍历所有传送起点 \(x\) 和传送终点 \(y\)，计算 \(dis[S][x]\) 和 \(dis[y][T]\)

然后累加上代价取第 \(m+1\) 小，时间复杂度 \(O(n^2)\)

考虑优化。

由于传送的代价都是一样的，因此求第 \(m+1\) 小的传送最短路径等价于求第 \(m+1\) 小的 \(dis[S][x]+dis[y][T]\)

我们预处理所有点到 \(S\) 和 \(T\) 的距离，排好序，将排好序的数组分别记作 \(a\) 和 \(b\)

该问题就变成了取所有 \(a_i+b_j\) 中的第 \(m+1\) 小

这是一个经典的问题，我们可以用堆处理

时间复杂度 \(O(m\cdot log n)\)

再次考虑优化。

我们换个角度思考，给定一个值，求有多少 \(a_i+b_j\) 比它小，怎么求？

这又是一个经典的问题，我们可以用双指针求出 ，这样我们只需要二分查找这个值就可以了

时间复杂度 \(O(n\cdot logn)\)

注意细节：也可以不传送，也可以走被封锁的路

code

#include<bits/stdc++.h>
using namespace std;

#define int long long

struct node
{
    int to, val;
};
vector<node> G[200005];

struct fresh
{
    int id, val;
} dis1[200005], dis2[200005], dis3[200005], dis4[200005];

void dfs1(int now, int fa, int val)
{
    dis1[now].val = val;
    dis1[now].id = now;

    dis3[now].val=val;
    dis3[now].id=now;

    for(auto next : G[now])
    {
        auto [to, len] = next;
        if(to == fa) continue;
        dfs1(to, now, val + len);
    }
}

void dfs2(int now, int fa, int val)
{
    dis2[now].val = val;
    dis2[now].id = now;

    dis4[now].val=val;
    dis4[now].id=now;
    for(auto next : G[now])
    {
        auto [to, len] = next;
        if(to == fa) continue;
        dfs2(to, now, val + len);
    }
}

struct unit
{
    int val, x, y;
    bool operator < (const unit &c) const
    {
        return c.val < val;
    }
};
const int inf = 1e9;

int n, m, k, s, t;

bool check(int x)
{
    int it2 = n;
    int sum = 0;
    for(int i = 1; i <= n; i++)
    {
        while(it2 && dis2[it2].val + dis1[i].val > x) it2--;
        sum += it2;
        if(!it2) break;

        for(auto next : G[dis1[i].id])
        {
            if(dis1[i].val + dis4[next.to].val <=x) sum--;//相邻节点无法传送
        }
        if(dis1[i].val + dis4[dis1[i].id].val <= x) sum--;
    }
    return sum>=m+1;
}

void solve()
{
    cin >> n >> m >> k >> s >> t;

    for(int i = 1; i < n; i++)
    {
        int x, y, w;
        cin >> x >> y >> w;
        G[x].push_back({y, w});
        G[y].push_back({x, w});
    }

    dfs1(s, s, 0);
    dfs2(t, t, 0);

    int ans = dis1[t].val; // 不传送，直接走树边

    sort(dis1 + 1, dis1 + 1 + n, [](auto b, auto c) { return b.val < c.val; });
    sort(dis2 + 1, dis2 + 1 + n, [](auto b, auto c) { return b.val < c.val; });

    ans=min(ans,dis1[1].val+dis2[1].val+(m?inf:k));//直接传送，不走树边

    int l = 0, r = 2e14;
    while(l + 1 < r)
    {
        int mid = (l + r) / 2;
        if(check(mid)) r = mid;
        else l = mid;
    }

    ans = min(ans, r + k);//传送和树边都走

    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int TT = 1;
    // cin >> TT;
    while(TT--) solve();
    return 0;
}