#include "Azer.h"
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
namespace {
std::string s;
std::vector<int> ans;
std::vector<bool> vis;
std::vector<std::vector<std::pair<int, int>>> adj;
std::priority_queue<std::pair<int, int>> pq;
int n;
int state = -1;
const int n_width = 10;
const int dist_width = 19;
void send(int u, int dist) {
SendA(0); // we are sending
for (int bt = 0; bt < n_width; ++bt) {
SendA(!!(u & (1 << bt)));
}
for (int bt = 0; bt < dist_width; ++bt) {
SendA(!!(dist & (1 << bt)));
}
}
std::pair<int, int> receive() {
std::pair<int, int> ans;
if (s.empty() or s[0] == '0') {
// other pq is empty
s.clear();
return {-int(1e9), -1};
}
for (int bt = 0; bt < n_width; ++bt) {
ans.second += (1 << bt) * (s[bt + 1] - '0');
}
for (int bt = 0; bt < dist_width; ++bt) {
ans.first += (1 << bt) * (s[bt + n_width + 1] - '0');
}
ans.first = -ans.first;
s.clear();
return ans;
}
} // namespace
void run_dijkstra() {
pq.push(receive()); // guranteed to not be visited
while (!pq.empty()) {
auto [dist, u] = pq.top();
if (u == -1) {
return;
}
if (!vis[u]) {
break;
}
pq.pop();
}
auto [dist, u] = pq.top();
vis[u] = true;
pq.pop();
dist = -dist;
ans[u] = std::min(ans[u], dist);
send(u, dist);
for (auto &[i, w] : adj[u]) {
pq.push({-(dist + w), i});
ans[i] = std::min(ans[i], dist + w);
}
SendA(1); // we want to receive
}
void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
std::vector<int> C) {
n = N;
adj = std::vector<std::vector<std::pair<int, int>>>(N);
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 = std::vector<int>(n, (1 << 30) - 1);
vis.resize(n);
ans[0] = 0;
pq.push({0, 0});
run_dijkstra();
}
void ReceiveA(bool x) {
s.push_back(x + '0');
if (state == -1) {
if (!x) {
run_dijkstra();
} else {
state = x;
}
return;
}
if (s.length() == n_width + dist_width + 1) {
state = -1;
run_dijkstra();
}
}
std::vector<int> Answer() { return ans; }
#include "Baijan.h"
#include <queue>
#include <string>
#include <vector>
namespace {
std::string s;
std::vector<std::vector<std::pair<int, int>>> adj;
std::vector<bool> vis;
std::priority_queue<std::pair<int, int>> pq;
int n;
int state = -1;
const int n_width = 10;
const int dist_width = 19;
void send_pq_top() {
while (!pq.empty()) {
auto [dist, u] = pq.top();
if (!vis[u]) {
break;
}
pq.pop();
}
if (pq.empty()) {
SendB(0); // pq is empty, nothng exists
return;
}
SendB(1); // pq is nonempty, followed by the info
auto [dist, u] = pq.top();
pq.pop();
dist = -dist;
for (int bt = 0; bt < n_width; ++bt) {
SendB(!!(u & (1 << bt)));
}
for (int bt = 0; bt < dist_width; ++bt) {
SendB(!!(dist & (1 << bt)));
}
}
// receive [u, dist]
std::pair<int, int> receive() {
std::pair<int, int> ans;
for (int bt = 0; bt < n_width; ++bt) {
ans.first += (1 << bt) * (s[bt] - '0');
}
for (int bt = 0; bt < dist_width; ++bt) {
ans.second += (1 << bt) * (s[bt + n_width] - '0');
}
s.clear();
return ans;
}
} // namespace
void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
std::vector<int> D) {
n = N;
adj = std::vector<std::vector<std::pair<int, int>>>(N);
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]});
}
vis.resize(n);
}
void ReceiveB(bool y) {
if (state == -1) {
if (!y) {
// azer is sending their info
state = 0;
} else {
// azer is requesting info
send_pq_top();
}
return;
}
s.push_back(y + '0');
if (s.length() == n_width + dist_width) {
auto [u, dist] = receive();
vis[u] = true;
for (auto &[i, w] : adj[u]) {
pq.push({-(dist + w), i});
}
state = -1;
}
}
