#include <bits/stdc++.h>
#include "Azer.h"
using namespace std;
const int NA = 2001;
const int INFA = (int)1e9;
int nA;
vector <int> distA;
vector <pair <int, int> > vA[NA];
set <pair <int, int> > readyA;
int mx_distA = 0, cntA = 0, completeA = 0, waiting_forA;
vector <int> curA;
void addA(int node, int d){
completeA++;
mx_distA += d;
distA[node] = mx_distA;
for(auto &i : vA[node]){
if(distA[node] + i.second < distA[i.first]){
readyA.insert(make_pair(distA[node] + i.second, i.first));
}
}
}
pair <int, int> get_nextA(){
while(readyA.size() && distA[readyA.begin()->second] != INFA){
readyA.erase(readyA.begin());
}
if(readyA.size()){
return make_pair(readyA.begin()->first - mx_distA, readyA.begin()->second);
}
return make_pair(511, 511);
}
void SendA(){
if(completeA == nA) return;
waiting_forA = 9;
pair <int, int> f = get_nextA();
for(int i = 8 ; i >= 0 ; i--){
SendA((f.first >> i) & 1);
}
}
void InitA(int N, int A, vector <int> U, vector <int> V, vector <int> C){
nA = N;
for(int i = 0 ; i < A ; i++){
vA[U[i]].push_back(make_pair(V[i], C[i]));
vA[V[i]].push_back(make_pair(U[i], C[i]));
}
distA.resize(N, INFA);
distA[0] = 0;
addA(0, 0);
SendA();
}
void ReceiveA(bool x){
if(curA.size() == 0) curA.push_back(0);
curA.back() = curA.back() * 2 + x;
cntA++;
if(cntA == waiting_forA){
if(waiting_forA == 9){
auto g = get_nextA();
if(g.first <= curA.back()){
for(int i = 10 ; i >= 0 ; i--){
SendA((g.second >> i) & 1);
}
curA.clear();
cntA = 0;
addA(g.second, g.first);
SendA();
}
else{
curA.push_back(0);
cntA = 0;
waiting_forA = 11;
}
}
else{
assert(curA.size() == 2);
addA(curA[1], curA[0]);
SendA();
curA.clear();
cntA = 0;
}
}
}
vector <int> Answer(){
return distA;
}
#include <bits/stdc++.h>
#include "Baijan.h"
using namespace std;
const int NB = 2001;
const int INFB = (int)1e9;
int nB;
vector <int> distB;
vector <pair <int, int> > vB[NB];
set <pair <int, int> > readyB;
int mx_distB = 0, cntB = 0, waiting_forB;
vector <int> curB;
void addB(int node, int d){
mx_distB += d;
distB[node] = mx_distB;
for(auto &i : vB[node]){
if(distB[node] + i.second < distB[i.first]){
readyB.insert(make_pair(distB[node] + i.second, i.first));
}
}
}
pair <int, int> get_nextB(){
while(readyB.size() && distB[readyB.begin()->second] != INFB){
readyB.erase(readyB.begin());
}
if(readyB.size()){
return make_pair(readyB.begin()->first - mx_distB, readyB.begin()->second);
}
return make_pair(511, 511);
}
void InitB(int N, int B, vector <int> S, vector <int> T, vector <int> D){
nB = N;
for(int i = 0 ; i < B ; i++){
vB[S[i]].push_back(make_pair(T[i], D[i]));
vB[T[i]].push_back(make_pair(S[i], D[i]));
}
distB.resize(N, INFB);
distB[0] = 0;
addB(0, 0);
waiting_forB = 9;
}
void ReceiveB(bool y){
if(curB.size() == 0) curB.push_back(0);
curB.back() = 2 * curB.back() + y;
cntB++;
if(cntB == waiting_forB){
if(waiting_forB == 9){
auto g = get_nextB();
if(g.first < curB.back()){
for(int i = 8 ; i >= 0 ; i--){
SendB((g.first >> i) & 1);
}
for(int i = 10 ; i >= 0 ; i--){
SendB((g.second >> i) & 1);
}
addB(g.second, g.first);
curB.clear();
cntB = 0;
waiting_forB = 9;
}
else{
for(int i = 8 ; i >= 0 ; i--){
SendB(1);
}
waiting_forB = 11;
curB.push_back(0);
cntB = 0;
}
}
else{
assert(curB.size() == 2);
addB(curB[1], curB[0]);
curB.clear();
cntB = 0;
waiting_forB = 9;
}
}
}
