形式化题意给定一张NNN个节点ABABAB条边的无向连通图边权是≤500\le 500≤500的正整数。Azer 知道其中AAA条边Baijan 知道另外BBB条。双方最多可以互相发送580005800058000比特信息需要共同求从000到所有节点的最短路。Solution将总通信次数均摊到每个节点得到5800029×2000(2×⌈log⁡2500⌉⌈log⁡22000⌉)×20005800029\times2000(2\times\lceil \log_2500\rceil\lceil \log_22000\rceil)\times 20005800029×2000(2×⌈log2​500⌉⌈log2​2000⌉)×2000。NNN很小而图很稠密我们可以考虑O(n2)O(n^2)O(n2)的朴素 Dijkstra。每次找当前蓝点中距离最小的点把它标记为白点并松弛它的所有出边。每一轮中两人只需分别找出本地距离最小的蓝点通过通信得出全局距离最小的蓝点然后分别在本地用该点进行松弛即可。因为边权≤500\le500≤500所以每一轮新白点的最短路与上一个白点最短路之差一定≤500\le 500≤500。双方互相发送距离增量只需2×92 \times 92×9比特。然后距离较小的人需要向另一人发送该点编号需要111111比特。恰好满足限制。CodeAzer.cpp#includeAzer.h#includevector#definerep(i,a,b)for(inti(a);ib;i)#definerept(i,a,b)for(inti(a);ib;i)#defineebemplace_backusingnamespacestd;namespace{constexprintMAXN2005,INF1e9;intN,u,t,lst,d[MAXN];boolf[MAXN],mk;vectorpairint,intg[MAXN];vectorboolbuf;}voidFindA(){u-1;rep(i,0,N)if(!f[i](u-1||d[i]d[u]))ui;if(u-1)return;td[u];rep(i,0,9)SendA((d[u]INF?511:d[u]-lst)i1);// 注意特判d[u]INF的情况}voidUpdA(){lstd[u]t,f[u]true;for(auto[v,w]:g[u])d[v]min(d[v],d[u]w);}voidReceiveA(boolb){buf.eb(b);if(!mkbuf.size()9){intx0;rep(i,0,9)x|buf[i]i;buf.clear();x511?xINF:xlst;if(tx){// 白点来自Arep(i,0,11)SendA(ui1);UpdA(),FindA();}elsetx,mktrue;}if(mkbuf.size()11){mkfalse,u0;rep(i,0,11)u|buf[i]i;buf.clear();UpdA(),FindA();}}voidInitA(int_N,intA,vectorintU,vectorintV,vectorintC){N_N;fill(d1,dN,INF);rep(i,0,A){g[U[i]].eb(V[i],C[i]);g[V[i]].eb(U[i],C[i]);}FindA();}vectorintAnswer(){returnvectorint(d,dN);}Baijan.cpp#includeBaijan.h#includevector#definerep(i,a,b)for(inti(a);ib;i)#definerept(i,a,b)for(inti(a);ib;i)#defineebemplace_backusingnamespacestd;namespace{constexprintMAXN2005,INF1e9;intN,u,t,lst,d[MAXN];boolf[MAXN],mk;vectorpairint,intg[MAXN];vectorboolbuf;}voidFindB(){u-1;rep(i,0,N)if(!f[i](u-1||d[i]d[u]))ui;if(u-1)return;td[u];rep(i,0,9)SendB((d[u]INF?511:d[u]-lst)i1);}voidUpdB(){lstd[u]t,f[u]true;for(auto[v,w]:g[u])d[v]min(d[v],d[u]w);}voidReceiveB(boolb){buf.eb(b);if(!mkbuf.size()9){intx0;rep(i,0,9)x|buf[i]i;buf.clear();x511?xINF:xlst;if(tx){// 白点来自Brep(i,0,11)SendB(ui1);UpdB(),FindB();}elsetx,mktrue;}if(mkbuf.size()11){mkfalse,u0;rep(i,0,11)u|buf[i]i;buf.clear();UpdB(),FindB();}}voidInitB(int_N,intB,vectorintU,vectorintV,vectorintC){N_N;fill(d1,dN,INF);rep(i,0,B){g[U[i]].eb(V[i],C[i]);g[V[i]].eb(U[i],C[i]);}FindB();}