P9650 [SNCPC2019] Escape Plan

StayAlone · 2025-04-10 20:27:45 · 题解

好难啊/ll

显然考虑从终点往起点走。

此题关键在于，反向行走时，若从 y\to x，正向实际上是 x\to y。

考虑 Dijkstra 的过程。反向跑图，从堆顶取出某最短路时，意味着正向走时存在一条从 x 往外的最优路线，此时耗费点 x 上的一次封锁就能堵住这条路线。

直到无法封锁，就求出了该点的真正最短路。时间复杂度与 Dijkstra 相同，\mathcal O(m\log m)。

AC record

int n, m, k, c[MAXN], e[MAXN], dis[MAXN];
priority_queue <pii> q; vector <pii> lnk[MAXN];

il void solve() {
    read(n, m, k);
    rer(i, 1, k, e); rer(i, 1, n, c);
    rep1(i, 1, n) dis[i] = -1, lnk[i].clear();
    rep1(i, 1, m) {
        int u, v, w; read(u, v, w);
        lnk[u].eb(v, w); lnk[v].eb(u, w);
    }
    rep1(i, 1, k) {
        int x = e[i]; c[x] = 0;
        q.emplace(0, x);
    }
    while (q.size()) {
        auto [d, x] = q.top(); q.pop();
        if (c[x]) {
            --c[x];
            continue;
        } d = -d;
        if (~dis[x]) continue;
        dis[x] = d;
        for (auto [v, w] : lnk[x]) if (!~dis[v]) q.emplace(-(d + w), v);
    } printf("%d\n", dis[1]);
}

int main() {
    for (int T = read(); T--; ) solve();
    return 0;
}