#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax = 2e3 + 5, inf = 1e9 + 5;
using pii = pair<int,int>;
namespace A {
int N;
set<pii> heap;
vector<pii> g[nmax];
int dist[nmax];
vector<int> bits;
int lastdocumented = 0;
int last = 0;
int state = 0;
int theircost = 0, theirnode = 0;
int mynode = 0, mycost = 0;
void receiveA(bool x) {
bits.emplace_back(x);
if(state == 0 && bits.size() == lastdocumented + 9) {
int node, cost;
if(heap.size())
tie(cost, node) = *heap.begin();
else
node = N, cost = 511 + last;
cost -= last;
theircost = 0;
for(int i = lastdocumented; i < bits.size(); i++) theircost = (theircost << 1) | bits[i];
lastdocumented = bits.size();
//cerr << "For A: " << node << ' ' << cost << "//" << theircost << '\n';
if(min(cost, theircost) == 511)
return;
//cerr << "arrived here " << lastdocumented << ' ' << theircost << ' ' << cost << ' ' << node << '\n';
if(theircost < cost) {
state = 1;
mycost = theircost;
return;
}
else {
for(int i = 10; i >= 0; i--) SendA((node & (1 << i)) > 0);
heap.erase(heap.begin());
mynode = node;
mycost = cost;
}
state = 2;
}
if(state == 1 && lastdocumented + 11 == bits.size()) {
mynode = 0;
for(int i = lastdocumented; i < bits.size(); i++)
mynode = (mynode << 1) | bits[i];
state = 2;
}
if(state == 2) {
auto [node, cost] = pii{mynode, mycost};
if(cost == 511)
return;
if(heap.count(pii{dist[node], node}))
heap.erase(heap.find(pii{dist[node], node}));
dist[node] = cost + last;
//cerr << "A continues with " << node << " + " << dist[node] << '\n';
//cerr << node << ' ' << cost + last << '\n';
for(auto [x, c] : g[node]) {
if(dist[x] > dist[node] + c) {
if(heap.count(pii{dist[x], x}))
heap.erase(heap.find(pii{dist[x], x}));
dist[x] = dist[node] + c;
heap.emplace(dist[x], x);
}
}
last = dist[node];
if(heap.size())
tie(cost, node) = *heap.begin();
else
node = N, cost = 511 + last;
//cerr << "A pushes: " << node << ' ' << cost << "/" << last << '\n';
cost -= last;
for(int i = 8; i >= 0; i--) SendA((cost & (1 << i)) > 0);
state = 0;
lastdocumented = bits.size();
}
}
} // namespace
void ReceiveA(bool x) { A::receiveA(x); }
void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
std::vector<int> C) {
A::N = N;
for (int i = 0; i < A; ++i) {
A::g[U[i]].emplace_back(V[i], C[i]);
A::g[V[i]].emplace_back(U[i], C[i]);
}
for(int i = 0; i < N; i++) A::dist[i] = inf;
A::dist[0] = 0;
A::heap.emplace(0, 0);
for(int i = 0; i < 9; i++)
SendA(0);
return;
}
std::vector<int> Answer() {
std::vector<int> ans(A::N);
for (int k = 0; k < A::N; ++k) {
ans[k] = A::dist[k];
}
return ans;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
#define nmax sdioh
#define inf sdiohah
const int nmax = 2e3 + 5, inf = 1e9 + 5;
using pii = pair<int,int>;
namespace B {
int N;
set<pii> heap;
vector<pii> g[nmax];
int dist[nmax];
vector<int> bits;
int lastdocumented = 0;
int last = 0;
int state = 0;
int theircost = 0, theirnode = 0;
int mynode = 0, mycost = 0;
void receiveB(bool x) {
bits.emplace_back(x);
if(state == 0 && bits.size() == lastdocumented + 9) {
int node, cost;
if(heap.size())
tie(cost, node) = *heap.begin();
else
node = N, cost = 511 + last;
cost -= last;
theircost = 0;
for(int i = lastdocumented; i < bits.size(); i++) theircost = (theircost << 1) | bits[i];
lastdocumented = bits.size();
//cerr << "For B: " << node << ' ' << cost << "//" << theircost << '\n';
if(min(cost, theircost) == 511)
return;
if(theircost <= cost) {
state = 1;
mycost = theircost;
return;
}
else {
for(int i = 10; i >= 0; i--) SendB((node & (1 << i)) > 0);
heap.erase(heap.begin());
mynode = node;
mycost = cost;
}
state = 2;
}
//else if(state == 1) { cerr << lastdocumented << ' ' << bits.size() << '\n'; }
if(state == 1 && lastdocumented + 11 == bits.size()) {
mynode = 0;
for(int i = lastdocumented; i < bits.size(); i++)
mynode = (mynode << 1) | bits[i];
state = 2;
}
if(state == 2) {
auto [node, cost] = pii{mynode, mycost};
if(cost == 511)
return;
if(heap.count(pii{dist[node], node}))
heap.erase(heap.find(pii{dist[node], node}));
dist[node] = cost + last;
//cerr << "B continues with " << node << " + " << dist[node] << '\n';
for(auto [x, c] : g[node]) {
if(dist[x] > dist[node] + c) {
if(heap.count(pii{dist[x], x}))
heap.erase(heap.find(pii{dist[x], x}));
dist[x] = dist[node] + c;
heap.emplace(dist[x], x);
}
}
last = dist[node];
if(heap.size())
tie(cost, node) = *heap.begin();
else
node = N, cost = 511 + last;
cost -= last;
for(int i = 8; i >= 0; i--) SendB((cost & (1 << i)) > 0);
state = 0;
lastdocumented = bits.size();
}
}
} // namespace
void ReceiveB(bool x) { B::receiveB(x); }
void InitB(int N, int B, std::vector<int> U, std::vector<int> V,
std::vector<int> C) {
B::N = N;
for (int i = 0; i < B; ++i) {
B::g[U[i]].emplace_back(V[i], C[i]);
B::g[V[i]].emplace_back(U[i], C[i]);
}
for(int i = 0; i < N; i++) B::dist[i] = inf;
B::dist[0] = 0;
B::heap.emplace(0, 0);
for(int i = 0; i < 9; i++)
SendB(0);
return;
}
