形式化题意
给定一张 \(N\) 个节点 \(A+B\) 条边的无向连通图，边权是 \(\le 500\) 的正整数。Azer 知道其中 \(A\) 条边，Baijan 知道另外 \(B\) 条。双方最多可以互相发送 \(58000\) 比特信息，需要共同求从 \(0\) 到所有节点的最短路。
Solution
将总通信次数均摊到每个节点，得到 \(58000=29\times2000=(2\times\lceil \log_2500\rceil+\lceil \log_22000\rceil)\times 2000\)。
\(N\) 很小，而图很稠密，我们可以考虑 \(O(n^2)\) 的朴素 Dijkstra。每次找当前蓝点中距离最小的点，把它标记为白点，并松弛它的所有出边。
每一轮中，两人只需分别找出本地距离最小的蓝点，通过通信得出全局距离最小的蓝点，然后分别在本地用该点进行松弛即可。
因为边权 \(\le500\)，所以每一轮新白点的最短路与上一个白点最短路之差一定 \(\le 500\)。双方互相发送距离增量只需 \(2 \times 9\) 比特。然后距离较小的人需要向另一人发送该点编号，需要 \(11\) 比特。恰好满足限制。
Code
Azer.cpp
#include "Azer.h"
#include <vector>
#define rep(i,a,b) for(int i(a);i<b;++i)
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define eb emplace_back
using namespace std;
namespace{constexpr int MAXN=2005,INF=1e9;int N,u,t,lst,d[MAXN];bool f[MAXN],mk;vector<pair<int,int>> g[MAXN];vector<bool> buf;
}
void FindA(){u=-1;rep(i,0,N) if(!f[i]&&(u==-1||d[i]<d[u])) u=i;if(u==-1) return;t=d[u];rep(i,0,9) SendA((d[u]==INF?511:d[u]-lst)>>i&1); // 注意特判d[u]=INF的情况
}
void UpdA(){lst=d[u]=t,f[u]=true;for(auto [v,w]:g[u]) d[v]=min(d[v],d[u]+w);
}
void ReceiveA(bool b){buf.eb(b);if(!mk&&buf.size()==9){int x=0;rep(i,0,9) x|=buf[i]<<i;buf.clear();x==511?x=INF:x+=lst;if(t<=x){ // 白点来自Arep(i,0,11) SendA(u>>i&1);UpdA(),FindA();}else t=x,mk=true;}if(mk&&buf.size()==11){mk=false,u=0;rep(i,0,11) u|=buf[i]<<i;buf.clear();UpdA(),FindA();}
}
void InitA(int _N,int A,vector<int> U,vector<int> V,vector<int> C){N=_N;fill(d+1,d+N,INF);rep(i,0,A){g[U[i]].eb(V[i],C[i]);g[V[i]].eb(U[i],C[i]);}FindA();
}
vector<int> Answer(){return vector<int>(d,d+N);
}
Baijan.cpp
#include "Baijan.h"
#include <vector>
#define rep(i,a,b) for(int i(a);i<b;++i)
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define eb emplace_back
using namespace std;
namespace{constexpr int MAXN=2005,INF=1e9;int N,u,t,lst,d[MAXN];bool f[MAXN],mk;vector<pair<int,int>> g[MAXN];vector<bool> buf;
}
void FindB(){u=-1;rep(i,0,N) if(!f[i]&&(u==-1||d[i]<d[u])) u=i;if(u==-1) return;t=d[u];rep(i,0,9) SendB((d[u]==INF?511:d[u]-lst)>>i&1);
}
void UpdB(){lst=d[u]=t,f[u]=true;for(auto [v,w]:g[u]) d[v]=min(d[v],d[u]+w);
}
void ReceiveB(bool b){buf.eb(b);if(!mk&&buf.size()==9){int x=0;rep(i,0,9) x|=buf[i]<<i;buf.clear();x==511?x=INF:x+=lst;if(t<x){ // 白点来自Brep(i,0,11) SendB(u>>i&1);UpdB(),FindB();}else t=x,mk=true;}if(mk&&buf.size()==11){mk=false,u=0;rep(i,0,11) u|=buf[i]<<i;buf.clear();UpdB(),FindB();}
}
void InitB(int _N,int B,vector<int> U,vector<int> V,vector<int> C){N=_N;fill(d+1,d+N,INF);rep(i,0,B){g[U[i]].eb(V[i],C[i]);g[V[i]].eb(U[i],C[i]);}FindB();
}