专栏文章

P9650 [SNCPC2019] Escape Plan

SStayAlone9.29Hz
P9650题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipnticg
此快照首次捕获于
2025/12/03 15:02
3 个月前
此快照最后确认于
2025/12/03 15:02
3 个月前
查看原文
好难啊/ll
显然考虑从终点往起点走。
此题关键在于，反向行走时，若从 y→xy\to x，正向实际上是 x→yx\to y。
考虑 Dijkstra 的过程。反向跑图，从堆顶取出某最短路时，意味着正向走时存在一条从 xx 往外的最优路线，此时耗费点 xx 上的一次封锁就能堵住这条路线。
直到无法封锁，就求出了该点的真正最短路。时间复杂度与 Dijkstra 相同，O(mlog⁡m)\mathcal O(m\log m)。
AC record
CPP
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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...