#include "Azer.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <queue>
#include <iostream>
using namespace std;
namespace {
int const nmax = 2000;
int const inf = nmax * 500;
int const cost_size = 9;
int const id_size = 11;
int global = 0;
vector<pair<int,int>> g[1 + nmax];
int n;
int dist[1 + nmax], forever[1 + nmax];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
}
namespace rec{
int _count = 0;
int wait;
int curr;
vector<int> history;
void waitfor(int _wait){
wait = _wait;
_count = 0;
curr = 0;
}
}
void refresh(){
while(0 < pq.size()){
int node = pq.top().second;
int cost = pq.top().first;
pq.pop();
if(cost == dist[node]){
for(int h = 0; h < g[node].size(); h++){
int to = g[node][h].first;
int edge = g[node][h].second;
if(dist[node] + edge < dist[to]){
dist[to] = dist[node] + edge;
pq.push({dist[to], to});
}
}
}
}
}
int best(){
int result = -1;
for(int i = 0;i < n; i++)
if(forever[i] == 0)
if(result == -1 || dist[i] < dist[result])
result = i;
return result;
}
void sendnumber(int val, int bits){
if((1 << bits) <= val)
val = (1 << bits) - 1;
for(int i = 0; i < bits; i++)
SendA(0 < (val & (1 << i)));
}
void InitA(int n, int m, vector<int> u, vector<int> v, vector<int> cost) {
::n = n;
for(int i = 0; i < m; i++){
g[u[i]].push_back({v[i], cost[i]});
g[v[i]].push_back({u[i], cost[i]});
}
for(int i = 0;i < n; i++)
dist[i] = inf;
dist[0] = 0;
pq.push({0, 0});
refresh();
sendnumber(dist[best()] - global, cost_size);
rec::waitfor(cost_size);
}
void ReceiveNumber(int number, int bits){
if(bits == cost_size){
int id = best();
int mine = dist[id] - global;
if(mine <= number) {
sendnumber(id, id_size);
global += mine;
forever[id] = 1;
if(best() != -1) {
sendnumber(dist[best()] - global, cost_size);
rec::waitfor(cost_size);
}
} else
rec::waitfor(id_size);
} else {
dist[number] = global + rec::history.back();
pq.push({dist[number], number});
forever[number] = 1;
refresh();
global += rec::history.back();
if(best() != -1) {
sendnumber(dist[best()] - global, cost_size);
rec::waitfor(cost_size);
}
}
rec::history.push_back(number);
}
void ReceiveA(bool x) {
rec::curr |= (x<<rec::_count);
rec::_count++;
if(rec::wait == rec::_count)
ReceiveNumber(rec::curr, rec::wait);
}
vector<int> Answer() {
vector<int> ans(n);
for (int k = 0; k < n; ++k)
ans[k] = dist[k];
return ans;
}
#include "Baijan.h"
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
namespace {
int const nmax = 2000;
int const inf = nmax * 500;
int const cost_size = 9;
int const id_size = 11;
int global = 0;
vector<pair<int,int>> g[1 + nmax];
int n;
int dist[1 + nmax], forever[1 + nmax];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
}
namespace req{
int _count = 0;
int wait;
int curr;
vector<int> history;
void waitfor(int _wait){
wait = _wait;
_count = 0;
curr = 0;
}
}
void refreshB(){
while(0 < pq.size()){
int node = pq.top().second;
int cost = pq.top().first;
pq.pop();
if(cost == dist[node]){
for(int h = 0; h < g[node].size(); h++){
int to = g[node][h].first;
int edge = g[node][h].second;
if(dist[node] + edge < dist[to]){
dist[to] = dist[node] + edge;
pq.push({dist[to], to});
}
}
}
}
}
int bestB(){
int result = -1;
for(int i = 0;i < n; i++)
if(forever[i] == 0)
if(result == -1 || dist[i] < dist[result])
result = i;
return result;
}
void sendnumberB(int val, int bits){
for(int i = 0; i < bits; i++)
SendB(0 < (val & (1 << i)));
}
void InitB(int n, int m, vector<int> u, vector<int> v, vector<int> cost) {
::n = n;
for(int i = 0; i < m; i++){
g[u[i]].push_back({v[i], cost[i]});
g[v[i]].push_back({u[i], cost[i]});
}
for(int i = 0;i < n; i++)
dist[i] = inf;
dist[0] = 0;
pq.push({0, 0});
refreshB();
req::waitfor(cost_size);
}
void ReceiveNumberB(int number, int bits){
if(bits == cost_size){
int id = bestB();
int mine = dist[id] - global;
sendnumberB(mine, cost_size);
if(mine < number) {
sendnumberB(id, id_size);
global += mine;
forever[id] = 1;
req::waitfor(cost_size);
} else
req::waitfor(id_size);
} else {
dist[number] = global + req::history.back();
pq.push({dist[number], number});
forever[number] = 1;
refreshB();
global += req::history.back();
req::waitfor(cost_size);
}
req::history.push_back(number);
}
void ReceiveB(bool x) {
req::curr |= (x<<req::_count);
req::_count++;
if(req::wait == req::_count)
ReceiveNumberB(req::curr, req::wait);
}
