#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
/**
3 stage:
- stage 1: send weight
- stage 2: compare weight, if smaller -> send node, else wait
- stage 3: mark (if weight is larger)
do n stages
**/
const int N=2222;
const int INF=1e9;
int nA,eA,cntStageA,curStageA; bool visA[N];
vector<int> disA;
vector<pair<int,int>> adjA[N];
void stage1A();
void stage2A();
void stage3A();
void InitA(int n, int a, vector<int> u, vector<int> v, vector<int> c){ /// input
nA=n; eA=a;
for(int i=0; i<a; ++i){
adjA[u[i]].emplace_back(v[i],c[i]);
adjA[v[i]].emplace_back(u[i],c[i]);
}
disA.resize(nA,INF);
disA[0]=0;
stage1A(); /// starting point
}
int cntrevA=0, revA=0, nxtdisA=0;
int curdisA=0, curverA=0;
void stage1A(){
if(cntStageA==nA) return;
++cntStageA;
int vdis=-1;
for(int i=0; i<nA; ++i) if(!visA[i]){
if(vdis==-1 || disA[vdis]>disA[i]){
vdis=i;
}
}
curverA=vdis; /// find the minimum distance from 0
for(int i=8; i>=0; --i){
if(disA[vdis]==INF) SendA(1);
else SendA((disA[vdis]-curdisA)>>i&1);
}
// cout<<disA[vdis]-curdisA<<'\n';
cntrevA=8, revA=0;
curStageA=2;
}
void stage2A(){
if(disA[curverA]-curdisA <= revA){
for(int i=10; i>=0; --i){
SendA(curverA>>i&1);
}
visA[curverA]=true;
for(auto [i,w]:adjA[curverA]){
disA[i]=min(disA[i],disA[curverA]+w);
}
curdisA=disA[curverA]; /// reupdate current min distance
stage1A(); /// start again
} else{
nxtdisA=revA+curdisA; /// will take minimum from opponent's
cntrevA=10, revA=0;
curStageA=3;
}
}
void stage3A(){
curdisA=nxtdisA;
disA[revA]=nxtdisA;
visA[revA]=true;
for(auto [i,w]:adjA[revA]){
disA[i]=min(disA[i],disA[revA]+w);
}
stage1A();
}
void ReceiveA(bool x){
if(x==1) revA|=(1<<cntrevA);
--cntrevA;
if(cntrevA==-1){
// cout<<curStageA<<'\n';
if(curStageA==2) stage2A();
else if(curStageA==3) stage3A();
else assert(0);
}
}
vector<int> Answer(){
return disA;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
const int N=2222;
const int INF=1e9;
int nB,eB,cntStageB,curStageB; bool visB[N];
vector<int> disB;
vector<pair<int,int>> adjB[N];
void stage1B();
void stage2B();
void stage3B();
void InitB(int n, int b, vector<int> s, vector<int> t, vector<int> d){
nB=n,eB=b;
for(int i=0; i<b; ++i){
adjB[s[i]].emplace_back(t[i],d[i]);
adjB[t[i]].emplace_back(s[i],d[i]);
}
disB.resize(nB,INF);
disB[0]=0;
stage1B();
}
int cntrevB=0, revB=0, nxtdisB=0;
int curdisB=0, curverB=0;
void stage1B(){
if(cntStageB==nB) return;
++cntStageB;
int vdis=-1;
for(int i=0; i<nB; ++i) if(!visB[i]){
if(vdis==-1 || disB[vdis]>disB[i]){
vdis=i;
}
}
curverB=vdis;
for(int i=8; i>=0; --i){
if(disB[vdis]==INF) SendB(1);
else SendB((disB[vdis]-curdisB)>>i&1);
}
cntrevB=8, revB=0;
curStageB=2;
}
void stage2B(){
// cout<<disB[curverB]<<" "<<curdisB<<'\n';
if(disB[curverB]-curdisB < revB){
for(int i=10; i>=0; --i){
SendB(curverB>>i&1);
// cout<<(curverB>>i&1)<<'\n';
}
visB[curverB]=true;
for(auto [i,w]:adjB[curverB]){
disB[i]=min(disB[i],disB[curverB]+w);
}
curdisB=disB[curverB];
stage1B();
} else{
nxtdisB=revB+curdisB;
cntrevB=10, revB=0;
curStageB=3;
}
}
void stage3B(){
curdisB=nxtdisB;
disB[revB]=nxtdisB;
visB[revB]=true;
for(auto [i,w]:adjB[revB]){
disB[i]=min(disB[i],disB[revB]+w);
}
stage1B();
}
void ReceiveB(bool x){
if(x==1) revB|=(1<<cntrevB);
--cntrevB;
if(cntrevB==-1){
if(curStageB==2) stage2B();
else if(curStageB==3) stage3B();
else assert(0);
}
}
