#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
struct Arc {
int nex, pds;
};
const int N = 2e3 + 42, INF = 1e6 + 42;
int n, knows[N];
vector<bool> msg;
vector<int> dist;
vector<Arc> arc[N];
priority_queue<pair<int, int>> pq;
void send(int i, int d) {
for(int j = 0; j < 11; j++)
SendA(i & (1 << j));
for(int j = 0; j < 20; j++)
SendA(d & (1 << j));
}
void InitA(int X, int a, vector<int> U, vector<int> V, vector<int> C) {
//cout << '\n' << '\n';
n = X;
dist.resize(n);
for(int i = 0; i < a; i++) {
arc[U[i]].push_back({V[i], C[i]});
arc[V[i]].push_back({U[i], C[i]});
}
for(int i = 1; i < n; i++)
knows[i] = dist[i] = INF;
for(int i = 0; i < n; i++)
pq.push({-dist[i], i});
send(0, 0);
}
void ReceiveA(bool x) {
msg.push_back(x);
if(31 == (int)msg.size()) {
int i = 0, d = 0;
for(int j = 0; j < 11; j++)
i += (1 << j) * msg[j];
for(int j = 0; j < 20; j++)
d += (1 << j) * msg[j + 11];
msg.clear();
if(d < dist[i]) {
dist[i] = d;
pq.push({-d, i});
}
knows[i] = d;
bool envoi = false;
while(!envoi && !pq.empty()) {
i = pq.top().second,
d = -pq.top().first;
pq.pop();
if(dist[i] == d) {
for(Arc a : arc[i]) {
if(dist[a.nex] > dist[i] + a.pds) {
dist[a.nex] = dist[i] + a.pds;
pq.push({-dist[a.nex], a.nex});
}
}
if(knows[i] > d) {
//cout << "Azer envoie " << i << ' ' << d << '\n';
knows[i] = d;
envoi = true;
send(i, d);
}
}
}
if(!envoi)
for(int j = 0; j < n; j++)
if(dist[j] == INF) {
//cout << "Azer n'envoie rien\n";
send(j, INF);
j = n;
}
}
}
vector<int> Answer() {
return dist;
}
#include <bits/stdc++.h>
#include "Baijan.h"
using namespace std;
struct Arc {
int nex, pds;
};
const int N = 2e3 + 42, INF = 1e6 + 42;
int n, knows[N];
vector<int> dist;
vector<Arc> arc[N];
vector<bool> msg;
priority_queue<pair<int, int>> pq;
void send(int i, int d) {
for(int j = 0; j < 11; j++)
SendB(i & (1 << j));
for(int j = 0; j < 20; j++)
SendB(d & (1 << j));
}
void InitB(int X, int b, vector<int> S, vector<int> T, vector<int> D) {
n = X;
dist.resize(n);
for(int i = 0; i < b; i++) {
arc[S[i]].push_back({T[i], D[i]});
arc[T[i]].push_back({S[i], D[i]});
}
for(int i = 1; i < n; i++)
knows[i] = dist[i] = INF;
for(int i = 0; i < n; i++)
pq.push({-dist[i], i});
}
void ReceiveB(bool y) {
msg.push_back(y);
if(31 == (int)msg.size()) {
int i = 0, d = 0;
for(int j = 0; j < 11; j++)
i += (1 << j) * msg[j];
for(int j = 0; j < 20; j++)
d += (1 << j) * msg[j + 11];
msg.clear();
if(d < dist[i]) {
dist[i] = d;
pq.push({-d, i});
}
knows[i] = d;
bool envoi = false;
while(!envoi && !pq.empty()) {
i = pq.top().second,
d = -pq.top().first;
pq.pop();
if(dist[i] == d) {
for(Arc a : arc[i]) {
if(dist[a.nex] > dist[i] + a.pds) {
dist[a.nex] = dist[i] + a.pds;
pq.push({-dist[a.nex], a.nex});
}
}
if(knows[i] > d) {
knows[i] = d;
//cout << "Baijan envoie " << i << ' ' << d << '\n';
envoi = true;
send(i, d);
}
}
}
if(!envoi)
for(int j = 0; j < n; j++)
if(dist[j] == INF) {
//cout << "Baijan n'envoie rien\n";
send(j, INF);
j = n;
}
}
}
