#include <algorithm>
#include <iostream>
#include "Azer.h"
using namespace std;
namespace {
const int N = 2000;
const int INF = 0x3f3f3f3f;
int *ej[N], *ew[N], eo[N], n;
int dd[N], pq[N], iq[N + 1], pq_cnt;
int d_, stage, ib, eb;
void append(int i, int j, int w) {
int o = eo[i]++;
if (!o) {
ej[i] = (int *) malloc(sizeof *ej[i]);
ew[i] = (int *) malloc(sizeof *ew[i]);
} else if (!(o & o - 1)) {
ej[i] = (int *) realloc(ej[i], (o << 1) * sizeof *ej[i]);
ew[i] = (int *) realloc(ew[i], (o << 1) * sizeof *ew[i]);
}
ej[i][o] = j;
ew[i][o] = w;
}
bool lt(int i, int j) {
return dd[i] < dd[j];
}
int p2(int p) {
return (p <<= 1) > pq_cnt ? 0 : p ^ (p < pq_cnt && lt(iq[p ^ 1], iq[p]));
}
void pq_up(int i) {
int j, p, q;
for (p = pq[i]; (q = p >> 1) && lt(i, j = iq[q]); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_dn(int i) {
int j, p, q;
for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_add_last(int i) {
iq[pq[i] = ++pq_cnt] = i;
}
void pq_remove(int i) {
int j = iq[pq_cnt--];
if (i != j)
pq[j] = pq[i], pq_up(j), pq_dn(j);
pq[i] = 0;
}
void dijkstra(int i) {
pq_remove(i);
for (int o = 0; o < eo[i]; o++) {
int j = ej[i][o], w = ew[i][o], d = dd[i] + w;
if (dd[j] > d) {
if (dd[j] == INF)
pq_add_last(j);
dd[j] = d, pq_up(j);
}
}
}
void run() {
if (!pq_cnt)
return;
int ea = dd[iq[1]] - d_;
cerr << "We try again. A sends over a proposal of " << ea << endl;
stage = 0;
for (int h = 8; h >= 0; h--)
SendA(ea >> h & 1);
}
void receive(bool x) {
if (stage == 0) {
cerr << "A has received a signal. " << x << endl;
stage++;
if (x) {
cerr << "A has received the signal that B likes his proposal and is now sending over details." << endl;
int ia = iq[1]; d_ = dd[ia];
dijkstra(ia);
for (int h = 10; h >= 0; h--)
SendA(ia >> h & 1);
run();
} else
ib = 0;
} else if (stage < 12) {
cerr << "A is reading bit number " << stage - 1 << " of B's ib." << endl;
ib = ib << 1 ^ x, stage++;
if (stage == 12)
eb = 0;
} else {
cerr << "A is reading bit number " << stage - 12 << " of B's eb." << endl;
eb = eb << 1 ^ x, stage++;
if (stage == 21) {
cerr << "A has completed reading B's proposal" << endl;
d_ += eb;
if (dd[ib] > d_) {
if (dd[ib] == INF)
pq_add_last(ib);
dd[ib] = d_, pq_up(ib);
}
dijkstra(ib);
cerr << "Here we go again." << endl;
run();
}
}
}
void init(int m, vector<int> ii, vector<int> jj, vector<int> ww) {
for (int h = 0; h < m; h++) {
int i = ii[h], j = jj[h], w = ww[h];
append(i, j, w), append(j, i, w);
}
for (int i = 0; i < n; i++)
dd[i] = INF;
dd[0] = 0, pq_add_last(0);
run();
}
}
void InitA(int n, int m, vector<int> ii, vector<int> jj, vector<int> ww) {
::n = n, init(m, ii, jj, ww);
}
void ReceiveA(bool x) {
receive(x);
}
vector<int> Answer() {
vector<int> ans(n);
for (int i = 0; i < n; i++)
ans[i] = dd[i];
return ans;
}
#include <algorithm>
#include <iostream>
#include "Baijan.h"
using namespace std;
namespace {
const int N = 2000;
const int INF = 0x3f3f3f3f;
int *ej[N], *ew[N], eo[N], n;
int dd[N], pq[N], iq[N + 1], pq_cnt;
int d_, stage, ia, ea;
void append(int i, int j, int w) {
int o = eo[i]++;
if (!o) {
ej[i] = (int *) malloc(sizeof *ej[i]);
ew[i] = (int *) malloc(sizeof *ew[i]);
} else if (!(o & o - 1)) {
ej[i] = (int *) realloc(ej[i], (o << 1) * sizeof *ej[i]);
ew[i] = (int *) realloc(ew[i], (o << 1) * sizeof *ew[i]);
}
ej[i][o] = j;
ew[i][o] = w;
}
bool lt(int i, int j) {
return dd[i] < dd[j];
}
int p2(int p) {
return (p <<= 1) > pq_cnt ? 0 : p ^ (p < pq_cnt && lt(iq[p ^ 1], iq[p]));
}
void pq_up(int i) {
int j, p, q;
for (p = pq[i]; (q = p >> 1) && lt(i, j = iq[q]); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_dn(int i) {
int j, p, q;
for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_add_last(int i) {
iq[pq[i] = ++pq_cnt] = i;
}
void pq_remove(int i) {
int j = iq[pq_cnt--];
if (i != j)
pq[j] = pq[i], pq_up(j), pq_dn(j);
pq[i] = 0;
}
void dijkstra(int i) {
pq_remove(i);
for (int o = 0; o < eo[i]; o++) {
int j = ej[i][o], w = ew[i][o], d = dd[i] + w;
if (dd[j] > d) {
if (dd[j] == INF)
pq_add_last(j);
dd[j] = d, pq_up(j);
}
}
}
void receive(bool x) {
if (stage < 9) {
ea = ea << 1 ^ x, stage++;
if (stage == 9) {
int ib = iq[1], eb = dd[ib] - d_;
cerr << "B received a suggestion for a distance of " << d_ + ea << " compared to his own " << dd[ib] << endl;
if (ea < eb) {
cerr << "B starts receiving. Going into Stage 9." << endl;
ia = 0, SendB(1);
} else {
cerr << "B uses his own proposal and sends the details to A: " << ib << ' ' << dd[ib] << endl;
d_ = dd[ib];
dijkstra(ib);
cerr << "New proposal: " << iq[1] << ' ' << dd[iq[1]] << endl;
stage = ea = 0;
SendB(0);
for (int h = 10; h >= 0; h--)
SendB(ib >> h & 1);
for (int h = 8; h >= 0; h--)
SendB(eb >> h & 1);
}
}
} else {
cerr << "B receiving index stage " << stage << endl;
ia = ia << 1 ^ x, stage++;
if (stage == 20) {
cerr << "B got to stage 20 wowzahs" << endl;
d_ += ea;
if (dd[ia] > d_) {
if (dd[ia] == INF)
pq_add_last(ia);
dd[ia] = d_, pq_up(ia);
}
dijkstra(ia);
stage = ea = 0;
}
}
}
void init(int m, vector<int> ii, vector<int> jj, vector<int> ww) {
for (int h = 0; h < m; h++) {
int i = ii[h], j = jj[h], w = ww[h];
append(i, j, w), append(j, i, w);
}
for (int i = 0; i < n; i++)
dd[i] = INF;
dd[0] = 0, pq_add_last(0);
}
}
void InitB(int n, int m, vector<int> ii, vector<int> jj, vector<int> ww) {
::n = n, init(m, ii, jj, ww);
}
void ReceiveB(bool x) {
receive(x);
}
