题意

通信题。有一张 $N$ ($1\le N\le 2000$) 个点 $A+B$ ($1\le A,B\le 5\cdot10^5$) 条边的无向连通图，小 A 和小 B 分别分别知道这些边当中的 $A$ 条和 $B$ 条。每条边有权值 $C_i$ ($1\le C_i\le 500$)。两人之间可以互相发至多 $58000$ bits 的信息。求原图中 $0$ 到每个点的最短路。

题解

用 Dijkstra 算法求最短路，两人只需要比较下一个扩展的点的距离，选择较小的一个扩展即可。两个人互相发送距离需要 $2\cdot9$ bits (因为只需要发送距离减去上一个扩展的点的距离，这个数是不超过 $C_i$ 的非负整数，如果其中一个人没有可扩展的点则设为 $2^9-1$ 即可)，其中距离较小的人向另一个人发送编号需要 $11$ bits。因此每次扩展需要的 bits 数量为 $29$，总 bits 数量为 $29N\le 58000$ (因为第一次不需要交换信息所以其实是 $29(N-1)$)。

代码

// Azer.cpp
#include "Azer.h"
#include <limits>
#include <tuple>
#include <algorithm>
namespace {
int n, maxDis, toReceive, myDis, otherDis, toUpdate;
int *result;
std::vector<int> dis;
std::vector<bool> vis;
std::vector<std::vector<std::pair<int, int>>> e;
std::pair<int, int> findNext() {
    std::pair<int, int> res(maxDis + 501, n);
    for (int i = 0; i < n; ++i)
        if (!vis[i])
            res = std::min(res, std::make_pair(dis[i], i));
    res.first -= maxDis;
    return res;
}
void send(int x, int d) {
    for (int i = d - 1; i >= 0; --i)
        SendA(x >> i & 1);
}
void receive(int &x, int d) {
    toReceive = d;
    result = &x;
    x = 0;
}
void update(int u) {
    maxDis = dis[u];
    vis[u] = true;
    for (auto p : e[u]) {
        int v, l;
        std::tie(v, l) = p;
        dis[v] = std::min(dis[v], dis[u] + l);
    }
    if (!std::count(vis.begin(), vis.end(), false))
        return;
    auto p = findNext();
    myDis = p.first;
    toUpdate = p.second;
    send(myDis, 9);
    receive(otherDis, 9);
}
}
void InitA(int _n, int m, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
    n = _n;
    dis.assign(n, std::numeric_limits<int>::max());
    vis.resize(n);
    e.resize(n);
    dis[0] = 0;
    for (int i = 0; i < m; ++i) {
        e[u[i]].emplace_back(v[i], c[i]);
        e[v[i]].emplace_back(u[i], c[i]);
    }
    update(0);
}
void ReceiveA(bool x) {
    *result = 2 * *result + x;
    --toReceive;
    if (toReceive == 0) {
        if (result == &otherDis) {
            if (myDis <= otherDis) {
                send(toUpdate, 11);
                update(toUpdate);
            } else {
                receive(toUpdate, 11);
            }
        } else {
            dis[toUpdate] = maxDis + otherDis;
            update(toUpdate);
        }
    }
}
std::vector<int> Answer() {
    return dis;
}

// Baijan.cpp
#include "Baijan.h"
#include <limits>
#include <tuple>
#include <algorithm>
namespace {
int n, maxDis, toReceive, myDis, otherDis, toUpdate;
int *result;
std::vector<int> dis;
std::vector<bool> vis;
std::vector<std::vector<std::pair<int, int>>> e;
std::pair<int, int> findNext() {
    std::pair<int, int> res(maxDis + 501, n);
    for (int i = 0; i < n; ++i)
        if (!vis[i])
            res = std::min(res, std::make_pair(dis[i], i));
    res.first -= maxDis;
    return res;
}
void send(int x, int d) {
    for (int i = d - 1; i >= 0; --i)
        SendB(x >> i & 1);
}
void receive(int &x, int d) {
    toReceive = d;
    result = &x;
    x = 0;
}
void update(int u) {
    maxDis = dis[u];
    vis[u] = true;
    for (auto p : e[u]) {
        int v, l;
        std::tie(v, l) = p;
        dis[v] = std::min(dis[v], dis[u] + l);
    }
    if (!std::count(vis.begin(), vis.end(), false))
        return;
    auto p = findNext();
    myDis = p.first;
    toUpdate = p.second;
    send(myDis, 9);
    receive(otherDis, 9);
}
}
void InitB(int _n, int m, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
    n = _n;
    dis.assign(n, std::numeric_limits<int>::max());
    vis.resize(n);
    e.resize(n);
    dis[0] = 0;
    for (int i = 0; i < m; ++i) {
        e[u[i]].emplace_back(v[i], c[i]);
        e[v[i]].emplace_back(u[i], c[i]);
    }
    update(0);
}
void ReceiveB(bool x) {
    *result = 2 * *result + x;
    --toReceive;
    if (toReceive == 0) {
        if (result == &otherDis) {
            if (myDis < otherDis) {
                send(toUpdate, 11);
                update(toUpdate);
            } else {
                receive(toUpdate, 11);
            }
        } else {
            dis[toUpdate] = maxDis + otherDis;
            update(toUpdate);
        }
    }
}