TIOJ 2049：龜兔賽跑

TIOJ 2049：龜兔賽跑

題目大意：給一個 $n$ 點 $m$ 邊的無向帶權連通圖，要從 $s$ 走到 $t$，問移除掉一個點之後在 $s$ 仍然能走到 $t$ 的前提下，最短距離最長可以是多少，且輸出移除點的編號最小值，若沒有合法的移除方式，輸出 -1 與最短距離。

解法：參考了這題的題解，總共可以分成三種情況。

先求出 $s$ 到各點的最短距離 $dS(x)$ 與 $t$ 到各點的距離 $dT(x)$，可以得到一條最短路徑 $P(P_1=s,P_{|P|}=t)$，令 $S(x)$ 為最小的 $i$ 使得 $s\to P_i\to x$ 是最短路徑，$T(x)$ 為最大的 $i$ 使得 $t\to P_i\to x$ 是最短路徑。

現在對 $P$ 上的點維護一棵線段樹，代表的是移除路徑上某個點後最短路徑的最小值可以是多少。對於一個點 $x$，$s\to P_{S(x)}\to x\to P_{T(x)}\to t$ 這條路徑不會經過 $P_{S(x)+1}\sim P_{T(x)-1}$，代表拔掉 $[S(x)+1,T(x)-1]$ 這段區間裡的任何一點後可以走這條路徑，所以可以對這個區間更新 $dS(x)+dT(x)$；而對於一條邊 $(a,b)$，路徑是 $s\to P_{S(a)}\to a\to b\to P_{T(b)}\to t$ 則可以對區間 $[S(a)+1,T(b)-1]$ 更新 $dS(a)+d(a,b)+dT(b)$。

現在已經考慮完兩種情況了，剩下的就是當 $S(x)=T(x)$ 時，不經過 $P_{S(x)}$ 的最短路徑，可以對每個點求出 $nS(x),nT(x)$，代表從 $s,t$ 出發不經過 $S(x),T(x)$ 的最短距離。

上面三種情況會蓋到所有情況（證明可以看官解 ><），然後有一個小地方要考慮，不一定要移除 $P$ 上面的點，可以移除 $P$ 以外的點，然後距離維持是最短距離。

$\text{Code：}$

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

using ll = long long;

const ll INF = 1e18;
const int N = 3e5 + 5;

int n, m, s, t;
ll ans = -1;
int ansp;
vector<pair<int, int>> adj[N];

ll dS[N], dT[N];
int S[N], T[N], pre[N];

int sz, path[N];
bool inp[N];
ll nS[N], nT[N];

ll mn[4 * N];
void upd(int pos, int l, int r, int L, int R, ll x) {
    if (l > r) return;
    if (l == L && r == R) {
        mn[pos] = min(mn[pos], x);
        return;
    }
    int mid = (L + R) / 2;
    if (r <= mid) upd(pos * 2, l, r, L, mid, x);
    else if (l > mid) upd(pos * 2 + 1, l, r, mid + 1, R, x);
    else {
        upd(pos * 2, l, mid, L, mid, x);
        upd(pos * 2 + 1, mid + 1, r, mid + 1, R, x);
    }
}

void cald(ll *dis, int s, bool calp) {
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    fill(dis + 1, dis + n + 1, INF);
    dis[s] = 0;
    pq.emplace(0, s);
    while (pq.size()) {
        auto [d, pos] = pq.top();
        pq.pop();
        if (d > dis[pos]) continue;
        for (auto [np, w] : adj[pos]) if (d + w < dis[np]) {
            dis[np] = d + w;
            pq.emplace(dis[np], np);
            if (calp) pre[np] = pos;
        }
    }
}

void cals(int *S, ll *dis, bool isT) {
    for (int i = 1; i <= sz; i++) S[path[i]] = (isT ? sz - i + 1 : i);
    auto dfs = [&](auto dfs, int pos)->void {
        for (auto [np, w] : adj[pos]) if (!S[np] && dis[pos] + w == dis[np]) {
            S[np] = S[pos];
            dfs(dfs, np);
        }
    };
    for (int i = 1; i <= sz; i++) dfs(dfs, path[i]);
}

void caln(ll *nS, int *S, ll *dis, bool isT) {
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> pq;
    fill(nS + 1, nS + n + 1, INF);
    for (int i = 1; i <= n; i++) for (auto [j, w] : adj[i]) if (!inp[j] && S[i] != S[j] && S[i] < S[j] ^ isT && dis[i] + w < nS[j]) {
        nS[j] = dis[i] + w;
        pq.emplace(nS[j], S[j], j);
    }
    while (pq.size()) {
        auto [d, s, pos] = pq.top();
        pq.pop();
        if (d > nS[pos]) continue;
        for (auto [np, w] : adj[pos]) if (!inp[np] && s == S[np] && d + w < nS[np]) {
            nS[np] = d + w;
            pq.emplace(nS[np], s, np);
        }
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m >> s >> t;
    while (m--) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].emplace_back(b, w);
        adj[b].emplace_back(a, w);
    }

    cald(dS, s, 1);
    cald(dT, t, 0);
    for (int i = t; i; i = pre[i]) path[++sz] = i, inp[i] = 1;
    cals(T, dT, 1);
    reverse(path + 1, path + sz + 1);
    cals(S, dS, 0);

    fill(mn + 1, mn + 4 * sz + 1, INF);
    for (int i = 1; i <= n; i++) {
        upd(1, S[i] + 1, T[i] - 1, 1, sz, dS[i] + dT[i]);
        for (auto [j, w] : adj[i]) upd(1, S[i] + 1, T[j] - 1, 1, sz, dS[i] + w + dT[j]);
    }

    caln(nS, S, dS, 0);
    caln(nT, T, dT, 1);
    for (int i = 1; i <= n; i++) if (!inp[i] && S[i] == T[i] && nS[i] != INF && nT[i] != INF) upd(1, S[i], S[i], 1, sz, nS[i] + nT[i]);

    auto dfs = [&](auto dfs, int pos, int l, int r, ll cur)->void {
        cur = min(cur, mn[pos]);
        if (l == r) {
            if (cur != INF) {
                if (cur == ans) ansp = min(ansp, path[l]);
                if (cur > ans) ans = cur, ansp = path[l];
            }
            return;
        }
        int mid = (l + r) / 2;
        dfs(dfs, pos * 2, l, mid, cur);
        dfs(dfs, pos * 2 + 1, mid + 1, r, cur);
    };

    for (int i = 1; i <= n; i++) if (!inp[i]) {
        ans = dS[t];
        ansp = i;
        break;
    }
    dfs(dfs, 1, 1, sz, INF);
    if (ans == -1) {
        cout << "-1 " << dS[t] << '\n';
        return 0;
    }
    cout << ansp << ' ' << ans << '\n';
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！