#include "Azer.h"
#include<bits/stdc++.h>
using namespace std;
inline bool getbit(int num, int bit)
{
return (num >> bit)&1;
}
inline int lg(int x)
{
if(x == 1) return 1;
else return __lg(x-1) + 1;
}
/**/
vector<array<int, 2>> ad[2005];
vector<int> remain;
int dis[2005], n, m;
/**/
void recal(int u)
{
for(auto &[v, c] : ad[u]) if(dis[v] > dis[u] + c) dis[v] = dis[u] + c;
}
/**/
int last_val = 0, min_idx = 0, phase = 0;
void start_a_phase()
{
if(remain.size() == 0) return;
//cerr<<"A started a new phase"<<endl;
min_idx = 0;
for(int i = 0; i < remain.size(); i++) if(dis[remain[min_idx]] > dis[remain[i]]) min_idx = i;
//9 bits
int num = dis[remain[min_idx]] - last_val; if(num > 500) num = 501;
phase = 0;
for(int i = 0; i < 9; i++) SendA(getbit(num, i));
}
/**/
void InitA(int nn, int mm, vector<int> U, vector<int> V, vector<int> C) {
n = nn; m = mm;
for(int i = 0; i < m; i++){
ad[U[i]].push_back({V[i], C[i]});
ad[V[i]].push_back({U[i], C[i]});
}
memset(dis, 0x3f, sizeof(dis));
dis[0] = 0;
for(int i = 1; i < n; i++) remain.push_back(i);
recal(0);
start_a_phase();
}
/**/
int curval = 0, num = 0;
void ReceiveA(bool x)
{
if(phase == 0){
if(x == 1) curval += (1 << num);
num++;
if(num == 9){
if(curval >= dis[remain[min_idx]] - last_val){
//cerr<<"A agree me:"<<remain[min_idx]<<" "<<dis[remain[min_idx]]<<endl;
//Send our current best node
int d = lg(remain.size());
recal(remain[min_idx]); last_val = dis[remain[min_idx]];
remain.erase(remain.begin() + min_idx);
curval = num = 0;
for(int i = 0; i < d; i++) SendA(getbit(min_idx, i));
start_a_phase();
}
else{
phase = 1; last_val += curval;
//cerr<<"A change to hearing phase "<<curval<<" "<<dis[remain[min_idx]] - last_val<<endl;
}
curval = num = 0;
}
}
else{
if(x == 1) curval += (1 << num);
num++;
int d = lg(remain.size());
if(num == d){
//Receive B best node
int u = remain[curval];
//cerr<<"A Hearing finished"<<endl;
//cerr<<"A agree them:"<<u<<" "<<last_val<<endl;
remain.erase(remain.begin() + curval);
dis[u] = last_val; recal(u);
phase = 0; curval = num = 0;
start_a_phase();
}
}
}
vector<int> Answer() {
vector<int> ans(n);
for(int i = 0; i < n; i++) ans[i] = dis[i];
return ans;
}
#include "Baijan.h"
#include<bits/stdc++.h>
using namespace std;
inline bool getbit2(int num, int bit)
{
return (num >> bit)&1;
}
inline int lg2(int x)
{
if(x == 1) return 1;
else return __lg(x-1) + 1;
}
/**/
vector<array<int, 2>> ad2[2005];
vector<int> remain2;
int dis2[2005], n2, m2;
/**/
void recal2(int u)
{
for(auto &[v, c] : ad2[u]) if(dis2[v] > dis2[u] + c) dis2[v] = dis2[u] + c;
}
void InitB(int nn, int mm, vector<int> U, vector<int> V, vector<int> C) {
n2 = nn; m2 = mm;
for(int i = 0; i < m2; i++){
ad2[U[i]].push_back({V[i], C[i]});
ad2[V[i]].push_back({U[i], C[i]});
}
memset(dis2, 0x3f, sizeof(dis2));
dis2[0] = 0;
for(int i = 1; i < n2; i++) remain2.push_back(i);
recal2(0);
}
int last_val2 = 0, phase2 = 0, curval2 = 0, num2 = 0;
void ReceiveB(bool y) {
if(phase2 == 0){
if(y == 1) curval2 += (1 << num2);
num2++;
if(num2 == 9){
int min_idx = 0;
for(int i = 1; i < remain2.size(); i++) if(dis2[remain2[min_idx]] > dis2[remain2[i]]) min_idx = i;
int num = dis2[remain2[min_idx]] - last_val2; if(num > 500) num = 501;
for(int i = 0; i < 9; i++) SendB(getbit2(num, i));
if(num < curval2){
//Now we send our best node
last_val2 = dis2[remain2[min_idx]];
recal2(remain2[min_idx]);
int d = lg2(remain2.size());
//cerr<<"B agree me: "<<remain2[min_idx]<<" "<<last_val2<<" "<<remain2.size()<<endl;
phase2 = curval2 = num2 = 0;
for(int i = 0; i < d; i++) SendB(getbit2(min_idx, i));
remain2.erase(remain2.begin() + min_idx);
}
else{
//cerr<<"B change to hearing phase "<<curval2<<" "<<num2<<endl;
phase2 = 1; last_val2 += curval2;
}
curval2 = num2 = 0;
}
}
else{
if(y == 1) curval2 += (1 << num2);
num2++;
int d = lg2(remain2.size());
if(num2 == d){
/*Receive A best node*/
int u = remain2[curval2];
//cerr<<"B agree them: "<<u<<" "<<last_val2<<endl;
//cerr<<"B Hearing finished"<<endl;
remain2.erase(remain2.begin() + curval2);
dis2[u] = last_val2; recal2(u);
phase2 = 0; curval2 = num2 = 0;
}
}
}
