AtCoder ABC250 EX

dij求“多源”最短

思路

据说有最小生成树的做法，但没看懂

考虑转化，用 dij 求出每个点的 $dis$ 表示”该点到最近的特殊点的距离“，这可以 $O(m \log m)$ 做到，然后对于每条边，其权值改为 $c_i’ = dis_{a_i} + dis_{b_i} + c_i$ ，然后，对于新图，两个点在 $t$ 时间内可达当且仅当两点之间的路径中所有权值 $c_i’ \le t$ ，可以用瓶颈生成树做，但直接离线 + 并查集更简单

关于上述转化的证明：

记 $dis(a, b)$ 表示“点 $a, b$ 的最短路径长”

必要性：

任取原图答案中某一条边 $(a, b, c)$ ，我们必然是通过关键点 $k_1$ 走到关键点 $k_2$ ，即 $dis(k_1, a) + c + dis(b, k_2) \le t$ ，由 $dis_{a_i}, dis_{b_i}$ 的最小性质不难得到 $dis_{a_i} + dis_{b_i} + c = c’ \le dis(k_1, a) + c + dis(b, k_2) \le t$
充分性：

只要 $c’ \le t$ ，我们一定可以“安全”走过对应的边，又因为新图中找到的路径联通了两个关键点，其间的边都是“安全”的，所以必定可以走到

时间复杂度 $O(m \log m)$

代码

#include <bits/stdc++.h>
using LL = long long;
const LL INF = 1e18;
const int N = 2e5 + 100;
int n, m, k, tq, fa[N], h[N], idx = 0, ct = 0;
struct Edge{ int ne, ver, w; } e[N << 1];
struct Edge2{ int u, v; LL w; } e2[N];
struct Q{ int x, y, id; LL t; } que[N];
LL dis[N];
bool vis[N], ans[N];
int get(int x){ return x == fa[x] ? x : fa[x] = get(fa[x]); }
void add(int x, int y, int z){ e[idx] = {h[x], y, z}, h[x] = idx++; }
void dij()
{
    memset(vis, false, sizeof vis);
    std::priority_queue< std::pair<LL, int> > q;
    for (int i = k + 1; i <= n; ++i) dis[i] = INF;
    for (int i = 1; i <= k; ++i) q.push({0, i});
    while (!q.empty())
    {
        int x = q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x] = true;
        for (int i = h[x], y; ~i; i = e[i].ne) if (!vis[y = e[i].ver])
            if (dis[y] > dis[x] + e[i].w) 
            {
                dis[y] = dis[x] + e[i].w;
                q.push({-dis[y], y});
            }
    }
}
void merge(int x, int y){ fa[get(x)] = get(y); }
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1, u, v, w; i <= m; ++i)
    {
        scanf("%d %d %d", &u, &v, &w);
        add(u, v, w), add(v, u, w);
    }
    dij();
    for (int i = 0; i < idx; i += 2)
    {
        int u = e[i].ver, v = e[i ^ 1].ver, w = e[i].w;
        e2[++ct] = {u, v, dis[u] + dis[v] + w};
    }
    std::sort(e2 + 1, e2 + ct + 1, [&](Edge2 a, Edge2 b){ return a.w < b.w; });
    scanf("%d", &tq);
    for (int i = 1; i <= tq; ++i)
    {
        scanf("%d %d %lld", &que[i].x, &que[i].y, &que[i].t);
        que[i].id = i;
    }
    std::sort(que + 1, que + tq + 1, [&](Q a, Q b){ return a.t < b.t; });
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1, j = 1; i <= tq; ++i)
    {
        for (; j <= ct && e2[j].w <= que[i].t; ++j) merge(e2[j].u, e2[j].v);
        ans[que[i].id] = get(que[i].x) == get(que[i].y);
    }
    for (int i = 1; i <= tq; ++i)
        if (ans[i]) puts("Yes");
        else puts("No");
    return 0;
}