量子 teleportation 题解

这道题要求我们找到从1号CPU到k号CPU的最快传输路径，其中传输耗时为$2^{\max(|x_i-x_j|, |y_i-y_j|)}$。由于指数函数的特性，我们需要优先选择$\max$值较小的路径，这是解题的关键思路。

算法思路

1. 距离度量：两个CPU之间的传输耗时由$\max(|x_i-x_j|, |y_i-y_j|)$决定，记为$d$。由于$2^d$随$d$指数增长，我们应优先选择$d$值小的路径。

2. 方向划分：将平面划分为8个方向，对每个CPU，计算到其他CPU在各个方向上的最小$d$值。

3. 状态表示：使用向量表示到达每个节点的路径"代价"，向量中的元素是按顺序排列的$d$值。比较两条路径时，按从大到小的顺序比较$d$值，先出现较小值的路径更优。

4. 优先队列：使用优先队列（最小堆）实现Dijkstra算法，每次选择当前代价最小的路径进行扩展。

5. 路径记录：通过par数组记录每个节点的前驱，最终从k号CPU回溯到1号CPU，得到完整路径。

代码实现

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

template<class A, class B>
bool chmin(A &a, const B &b) {
    return b < a ? a = b, 1 : 0;
}

int dir(int i, int j, int x, int y) {
    if (i == x) {
        return j < y ? 2 : 6;
    }

    if (j == y) {
        return i < x ? 4 : 0;
    }

    if (x > i && y > j) {
        return 3;
    }

    if (x < i && y < j) {
        return 7;
    }

    if (x > i && y < j) {
        return 5;
    }

    return 1;
}

vector<int> operator + (const vector<int> &a, int bit) {
    vector<int> res;

    for (int i = int(a.size()) - 1; i >= 0; --i) {
        if (a[i] == bit) {
            bit++;
            continue;
        }

        if (bit != -1 && bit < a[i]) {
            res.emplace_back(bit);
            bit = -1;
        }

        res.emplace_back(a[i]);
    }

    if (bit != -1) {
        res.emplace_back(bit);
    }

    reverse(res.begin(), res.end());
    return res;
}

bool operator < (const vector<int> &a, const vector<int> &b) {
    for (int it = 0; ; ++it) {
        if (it == b.size()) {
            return 0;
        }

        if (it == a.size()) {
            return 1;
        }

        if (a[it] > b[it]) {
            return 0;
        }

        if (a[it] < b[it]) {
            return 1;
        }
    }

    assert(0);
    return 0;
}

pair<int, int> signs[] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};

auto main() -> int {
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef LOCAL
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m, k;
    cin >> n >> m >> k;
    const int inf = 1e9;
    vector<int> x(k), y(k);

    for (int i = 0; i < k; ++i) {
        cin >> x[i] >> y[i];
        x[i]--;
        y[i]--;
    }

    vector<vector<int>> mn(k, vector<int>(8, inf)), nxt(k, vector<int>(8, -1));
    int node = k;
    vector<int> R, lR, rR, C, lC, rC;

    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < k; ++j) {
            if (i ^ j) {
                chmin(mn[i][dir(x[i], y[i], x[j], y[j])], max(abs(x[i] - x[j]), abs(y[i] - y[j])));
            }
        }

        for (int dr = 0; dr < 8; ++dr) {
            if (mn[i][dr] != inf) {
                auto [sx, sy] = signs[dr];
                int v = mn[i][dr];
                R.emplace_back(x[i] + sx * v);
                lR.emplace_back(y[i] + sy);
                rR.emplace_back(y[i] + sy * v);
                C.emplace_back(y[i] + sy * v);
                lC.emplace_back(x[i] + sx);
                rC.emplace_back(x[i] + sx * v);

                if (lR.back() > rR.back()) {
                    swap(lR.back(), rR.back());
                }

                if (lC.back() > rC.back()) {
                    swap(lC.back(), rC.back());
                }

                nxt[i][dr] = node++;
            }
        }
    }

    vector<vector<int>> res(node, {inf});
    vector<int> par(node, -1);
    using T = pair<vector<int>, int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    auto sweep = [&](set<pair<int, int>> &s, vector<set<pair<int, int>>> &c, vector<int> &a, int l, int r,
    vector<int> &ans, int u) {
        for (auto it = s.lower_bound({l, 0}); it != s.end() && (*it).first <= r; it = s.erase(it)) {
            auto &[x, v] = *it;
            c[x].erase({a[v], v});

            if (chmin(res[v], ans)) {
                pq.emplace(res[v], v);
                par[v] = u;
            }
        }
    };
    vector<set<pair<int, int>>> r(n), c(m);

    for (int i = 1; i < k; ++i) {
        r[x[i]].insert({y[i], i});
        c[y[i]].insert({x[i], i});
    }

    res[0] = {};
    pq.emplace(res[0], 0);

    while (pq.size()) {
        auto [dat, u] = pq.top();
        pq.pop();

        if (res[u] != dat) {
            continue;
        }

        if (u >= k) {
            u -= k;

            if (0 <= R[u] && R[u] < n) {
                sweep(r[R[u]], c, y, lR[u], rR[u], res[u + k], u + k);
            }

            if (0 <= C[u] && C[u] < m) {
                sweep(c[C[u]], r, x, lC[u], rC[u], res[u + k], u + k);
            }
        } else if (u != k - 1) {
            for (int dr = 0; dr < 8; ++dr) {
                if (mn[u][dr] != inf) {
                    int v = nxt[u][dr];
                    auto ans = res[u] + mn[u][dr];

                    if (chmin(res[v], ans)) {
                        par[v] = u;
                        pq.emplace(res[v], v);
                    }
                }
            }
        }
    }

    vector<int> ans;

    for (int i = k - 1; i != -1; i = par[i]) {
        if (i < k) {
            ans.emplace_back(i + 1);
        }
    }

    cout << ans.size() << "\n";

    for (int i = int(ans.size()) - 1; i >= 0; --i) {
        cout << ans[i] << " ";
    }
}

代码解析

1. 方向计算：dir函数将两个点的相对位置划分为8个方向，便于后续计算每个方向上的最小距离。

2. 向量操作：operator+用于在路径代价向量中添加新的距离值，并保持向量按从大到小排序；operator<定义了向量的比较规则，确保优先选择更优的路径。

3. 预处理：计算每个CPU在8个方向上到其他CPU的最小距离，并为每个有效方向创建中间节点。

4. Dijkstra算法：使用优先队列实现，每次取出当前代价最小的节点进行扩展。对于CPU节点，扩展到其8个方向的中间节点；对于中间节点，通过sweep函数扫描该方向上的所有CPU节点。

5. 路径重建：通过par数组回溯从k号CPU到1号CPU的路径，输出结果。

该算法巧妙利用了指数函数的特性，通过优先选择较小的$\max$值，确保找到最优路径，同时使用中间节点和扫描操作提高了算法效率。