#include "Azer.h"
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>
namespace {
std::string s;
int n, prev_ans, state, d_b;
std::vector<std::vector<std::pair<int, int>>> adj;
std::vector<int> ans;
std::vector<bool> vis;
std::vector<int> done_nodes;
std::pair<int, int> closest() {
std::pair<int, int> p = {-1, (1 << 30) - 1};
for (auto &u : done_nodes) {
for (auto &[i, w] : adj[u]) {
if (vis[i]) {
continue;
}
if (ans[u] + w < p.second) {
p = {i, ans[u] + w};
}
}
}
return p;
}
void send(int x, int width) {
// std::cout << "sending " << x << " from a" << std::endl;
for (int i = 0; i < width; ++i) {
SendA(!!(x & (1 << i)));
}
}
int receive(int width) {
int ans = 0;
for (int i = 0; i < width; ++i) {
ans += (1 << i) * (s[i] - '0');
}
s = s.substr(width, s.length());
return ans;
}
bool compare_closest() {
d_b = receive(9) + prev_ans;
if (d_b == 511 + prev_ans) {
d_b = (1 << 30) - 1;
}
auto [u, d] = closest();
if (d < d_b) {
send(d - prev_ans, 9);
send(u, 11);
done_nodes.push_back(u), vis[u] = true;
ans[u] = d;
prev_ans = d;
return false;
} else {
send(511, 9);
return true;
}
}
} // namespace
void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
std::vector<int> C) {
prev_ans = 0, state = 0, n = N;
adj.resize(n);
ans.resize(n, (1 << 30) - 1);
vis.resize(n);
done_nodes = {0};
for (int i = 0; i < A; ++i) {
adj[U[i]].push_back({V[i], C[i]});
adj[V[i]].push_back({U[i], C[i]});
}
ans[0] = 0;
vis[0] = true;
}
void ReceiveA(bool x) {
s.push_back(x + '0');
if (state == 0 and s.length() == 9) {
state = compare_closest();
} else if (state == 1 and s.length() == 11) {
int u = receive(11);
ans[u] = d_b;
done_nodes.push_back(u), vis[u] = true;
prev_ans = d_b;
state = 0;
}
}
std::vector<int> Answer() { return ans; }
#include "Baijan.h"
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>
namespace {
std::string s;
int n, prev_ans, u_cl, d_cl, state, found;
std::vector<std::vector<std::pair<int, int>>> adj;
std::vector<int> ans;
std::vector<bool> vis;
std::vector<int> done_nodes;
std::pair<int, int> closest() {
std::pair<int, int> p = {-1, (1 << 30) - 1};
for (auto &u : done_nodes) {
for (auto &[i, w] : adj[u]) {
if (vis[i]) {
continue;
}
if (ans[u] + w < p.second) {
p = {i, ans[u] + w};
}
}
}
return p;
}
void send(int x, int width) {
// std::cout << "sending " << x << " from b" << std::endl;
for (int i = 0; i < width; ++i) {
SendB(!!(x & (1 << i)));
}
}
int receive(int width) {
int ans = 0;
for (int i = 0; i < width; ++i) {
ans += (1 << i) * (s[i] - '0');
}
s = s.substr(width, s.length());
return ans;
}
void send_closest() {
if (found >= n) {
return;
}
found++;
auto [u, d] = closest();
u_cl = u, d_cl = d;
send(std::min(d_cl - prev_ans, 511), 9);
}
} // namespace
void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
std::vector<int> D) {
prev_ans = 0, state = 0, n = N, found = 1;
adj.resize(n);
ans.resize(n, (1 << 30) - 1);
vis.resize(n);
done_nodes = {0};
for (int i = 0; i < B; ++i) {
adj[S[i]].push_back({T[i], D[i]});
adj[T[i]].push_back({S[i], D[i]});
}
ans[0] = 0;
vis[0] = true;
send_closest();
}
// b sends dist
// a compares
// if a is smaller, a sends dist and node
// else a sends just the dist 511 and b sends node
void ReceiveB(bool y) {
s.push_back(y + '0');
if (state == 0 and s.length() == 9) {
int d = receive(9) + prev_ans;
if (d == 511 + prev_ans) {
send(u_cl, 11);
done_nodes.push_back(u_cl), vis[u_cl] = true;
ans[u_cl] = d_cl, prev_ans = d_cl;
send_closest();
} else {
prev_ans = d, state = 1;
}
} else if (state == 1 and s.length() == 11) {
int u = receive(11);
ans[u] = prev_ans;
done_nodes.push_back(u), vis[u] = true;
send_closest();
state = 0;
}
}
