「JOISC 2019 Day2」两种运输

https://www.cnblogs.com/zhoushuyu/p/10585809.html 几乎全都是抄zsy大佬代码的
在atcoder上提交的：https://atcoder.jp/contests/joisc2019/submissions/19770413
考虑不需要堆优化的dijkstra算法
每一轮操作流程如下

1. A将未确定最短路的点的距离的最小值传给B
2. B将未确定最短路的点的距离的最小值传给A
3. 这样A,B都知道谁的距离更小一些，距离更小的要将对应的点的标号传给对方

每轮消耗29个操作
注意它只保证了两个图并起来联通，单个的不保证。可以用511表示正无穷。

#include "transportations.h"
#include <bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);(i)<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);(i)>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
const int MAXN=2005,inf=(1<<30)-1;
struct node{
	int n,mxdis,dis[MAXN],cnt,d,fr,ans;
	bool vis[MAXN];
	vector<pair<int,int> >G[MAXN];
	pair<int,int>findnxt(){
		pair<int,int>res={inf,n};
		fp(i,0,n-1)if(!vis[i])res=min(res,{dis[i],i});
		if(res.first!=inf)res.first-=mxdis;
		return res;
	}
	void upd(int u,int D){
		dis[u]=mxdis=D;++ans;vis[u]=1;
		for(auto x:G[u]){
			int v=x.first,w=x.second;
			dis[v]=min(dis[v],dis[u]+w);
		}
	}
	void init(int nn){
		n=nn;
		fp(i,0,n-1)dis[i]=inf;
	}
}T1,T2;
void InitA(int n,int A,vector<int>U,vector<int>V,vector<int>C){
	T1.init(n);
	fp(i,0,A-1)T1.G[U[i]].push_back({V[i],C[i]}),T1.G[V[i]].push_back({U[i],C[i]});
	T1.upd(0,0);
	pair<int,int>tmp=T1.findnxt();tmp.first-=T1.mxdis;fp(i,0,8)SendA(tmp.first>>i&1);
}
void ReceiveA(bool x){
	if(T1.cnt<9){
		T1.d|=x<<T1.cnt;++T1.cnt;
		if(T1.cnt==9){
			pair<int,int>tmp=T1.findnxt();
			if(T1.d>tmp.first){
				fp(i,0,10)SendA(tmp.second>>i&1);
				T1.upd(tmp.second,T1.mxdis+tmp.first);T1.d=T1.fr=0;
				T1.cnt=0;if(T1.ans==T1.n)return;
				pair<int,int>tmp=T1.findnxt();fp(i,0,8)SendA(tmp.first>>i&1);
			}
			else ++T1.cnt;
		}
	}
	else{
		T1.fr|=x<<T1.cnt-10;++T1.cnt;
		if(T1.cnt==21){
			T1.upd(T1.fr,T1.mxdis+T1.d);T1.d=T1.fr=T1.cnt=0;
			if(T1.ans==T1.n)return;
			pair<int,int>tmp=T1.findnxt();fp(i,0,8)SendA(tmp.first>>i&1);
		}
	}
}
vector<int>Answer(){
	vector<int>res;
	fp(i,0,T1.n-1)res.push_back(T1.dis[i]);
	return res;
}
void InitB(int n,int A,vector<int>U,vector<int>V,vector<int>C){
	T2.init(n);
	fp(i,0,A-1)T2.G[U[i]].push_back({V[i],C[i]}),T2.G[V[i]].push_back({U[i],C[i]});
	T2.upd(0,0);
}
void ReceiveB(bool x){
	if(T2.cnt<9){
		T2.d|=x<<T2.cnt;++T2.cnt;
		if(T2.cnt==9){
			pair<int,int>tmp=T2.findnxt();fp(i,0,8)SendB(tmp.first>>i&1);
			if(T2.d>=tmp.first){
				fp(i,0,10)SendB(tmp.second>>i&1);
				T2.upd(tmp.second,T2.mxdis+tmp.first);T2.d=T2.fr=T2.cnt=0;
			}
			else ++T2.cnt;
		}
	}
	else{
		T2.fr|=x<<T2.cnt-10;++T2.cnt;
		if(T2.cnt==21){
			T2.upd(T2.fr,T2.mxdis+T2.d);T2.d=T2.fr=T2.cnt=0;
		}
	}
}