题解：P11915 [PA 2025] 瞬间传送 / Teleport

· · 题解

https://www.luogu.com.cn/problem/P11915

需要观察到一个很厉害的贪心策略：如果钦定所有点的距离不大于 r，且存在 d(i,j)>r。假设 一种满足条件的新边是 (u,v)（由于两者无序，不妨钦定 d(i,u)<d(i,v)），可以进行讨论：

  1. 此时最优路径为 $i\to u\to v\to j$，判断一下这种方案是否不大于 $r$ 就可以了。
  2. 此时不管是走 $i\to u\to v\to j$ 还是 $i\to v\to u\to j$ 都不如走已经存在的 $i\to u\to j$ 这条路径，也就是说如果要走新边，代价是一定比原距离大，更是比 $r$ 大的；也就是说，$(u,v)$ 不能解决 $(i,j)$ 之间的问题，假设就不成立了。

综上，只需要判断 i\to u\to v\to j\le r 是否成立，就可以判断 (u,v) 是否合法。从大到小枚举 r，同时维护当前依然合法的 (u,v)（显然是有单调性的），对于不合法的 (i,j)，枚举每个 i，维护 \max\{d(v,j)\}，精细实现（主要是利用各种均摊）一下就能 O(n^3)。

这里具体提一下需要摊的几个点：

  1. 枚举到 r 的时候用所有 d(i,j)=r+1 把 v 在 i 处的最大 d(v,j) 更新，方便后面 O(n) 地 check。摊出来是 O(n^3) 的。
  2. 枚举仍然处在合法队列里的 (u,v)，如果 check 合法，就说明对于当前 r 至少存在一个合法解，就可以 break 了；否则，把 (u,v) 弹出，继续 check 下一条边。这样每条边只会被弹出一次，而未弹出边的 check 次数最多是 O(n)；加上 O(n) 的 check，摊出来是 O(n^3) 的。
#include <bits/stdc++.h>
const int inf = 0x3f3f3f3f;
int main() {
#ifdef ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
    std::freopen(".in", "r", stdin);
    std::freopen(".out", "w", stdout);
#endif
    int T;
    for (std::cin >> T; T--; ) {
        int n;
        std::cin >> n;
        std::vector<std::vector<int> > g(n + 1, std::vector<int> (n + 1, inf));
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) {
                char t;
                std::cin >> t;
                if (t == '1' || i == j)
                    g[i][j] = t - '0';
            }
        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= n; ++i)
                if (i != k)
                    for (int j = 1; j <= n; ++j)
                        if (j != i && j != k)
                            g[i][j] = std::min(g[i][j], g[i][k] + g[k][j]);
        std::queue<std::pair<int, int> > q;
        std::vector<std::vector<std::pair<int, int> > > p(n + 1);
        std::vector<std::vector<int> > mx(n + 1, std::vector<int> (n + 1));
        for (int i = 1; i < n; ++i)
            for (int j = i + 1; j <= n; ++j) {
                q.emplace(i, j);
                p[g[i][j] - 1].emplace_back(i, j);
            }
        auto check = [&](int u, int v, int r) {
            for (int i = 1; i <= n; ++i) {
                if (g[u][i] > g[v][i])
                    std::swap(u, v);
                if (g[u][i] + mx[v][i] > r)
                    return false;
            }
            return true;
        };
        for (int r = n; r >= -1; --r) {
            for (auto [i, j] : p[r])
                for (int v = 1; v <= n; ++v) {
                    mx[v][i] = std::max(mx[v][i], g[v][j]);
                    mx[v][j] = std::max(mx[v][j], g[v][i]);
                }
            for (; !q.empty(); ) {
                auto [u, v] = q.front();
                if (!check(u, v, r))
                    q.pop();
                else
                    break;
            }
            if (q.empty()) {
                std::cout << r + 1 << '\n';
                break;
            }
        }
    }
    return 0;
}