#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
namespace Azer{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
const int N=2010;
int f[N], n, vis[N];
vector<pair<int, int>> g[N];
int buffer;
int buffer_size;
int waiting_size;
int last_value;
int remain;
int ceil_log2(){
return 32-__builtin_clz(remain);
}
int find_idx(int u){
int ans=0;
for (int i=0; i<u; ++i) ans+=!vis[i];
return ans;
}
int find_node(int idx){
int ans=0;
while (idx>=(!vis[ans])) idx-=!vis[ans], ++ans;
return ans;
}
void FakeSendA(int size, int data){
for (int i=size-1; i>=0; --i) SendA(data>>i&1);
}
void adjust_pq(){
while (pq.size() && vis[pq.top().second]) pq.pop();
}
void reset_buffer(){
buffer=0;
buffer_size=0;
}
void optimize(int _u=-1, int _f=-1){
--remain;
int u=-1;
if (_u==-1){
last_value=pq.top().first;
u=pq.top().second; pq.pop();
}else{
last_value=_f;
u=_u; f[u]=_f;
}
vis[u]=1;
for (auto &e:g[u]){
int v=e.first, w=e.second;
if (f[v]>f[u]+w) pq.emplace(f[v]=f[u]+w, v);
}
adjust_pq();
}
}
void InitA(int N, int A, vector<int> U, vector<int> V,
vector<int> C) {
Azer::n=N;
Azer::remain=N;
for (int i=0; i<A; ++i) Azer::g[U[i]].emplace_back(V[i], C[i]), Azer::g[V[i]].emplace_back(U[i], C[i]);
Azer::pq.emplace(Azer::f[0]=0, 0);
for (int i=1; i<N; ++i) Azer::pq.emplace(Azer::f[i]=(1<<20)-1, i);
if (Azer::pq.size()){
Azer::FakeSendA(9, (Azer::pq.top().first==((1<<20)-1)?511:Azer::pq.top().first));
Azer::waiting_size=1;
}
}
void ReceiveA(bool x) {
++Azer::buffer_size;
Azer::buffer<<=1; Azer::buffer|=x;
if (Azer::buffer_size==Azer::waiting_size){
if (Azer::waiting_size==1){
if (Azer::buffer==0){
Azer::FakeSendA(Azer::ceil_log2(), Azer::find_idx(Azer::pq.top().second));
Azer::optimize();
if (Azer::pq.size()){
Azer::FakeSendA(9, (Azer::pq.top().first==((1<<20)-1)?511:Azer::pq.top().first-Azer::last_value));
Azer::waiting_size=1;
}
}else{
Azer::waiting_size=9+Azer::ceil_log2();
}
}else{
int v=Azer::find_node(Azer::buffer&((1<<Azer::ceil_log2())-1)), f=(Azer::buffer>>Azer::ceil_log2())+Azer::last_value;
Azer::optimize(v, f);
if (Azer::pq.size()){
Azer::FakeSendA(9, (Azer::pq.top().first==((1<<20)-1)?511:Azer::pq.top().first-Azer::last_value));
Azer::waiting_size=1;
}
}
Azer::reset_buffer();
}
}
vector<int> Answer() {
return vector<int>(Azer::f, Azer::f+Azer::n);
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
namespace Baijan{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
const int N=2010;
int f[N], n, vis[N];
vector<pair<int, int>> g[N];
int buffer;
int buffer_size;
int waiting_size;
int last_value;
int remain;
int ceil_log2(){
return 32-__builtin_clz(remain);
}
int find_idx(int u){
int ans=0;
for (int i=0; i<u; ++i) ans+=!vis[i];
return ans;
}
int find_node(int idx){
int ans=0;
while (idx>=(!vis[ans])) idx-=!vis[ans], ++ans;
return ans;
}
void FakeSendB(int size, int data){
for (int i=size-1; i>=0; --i) SendB(data>>i&1);
}
void adjust_pq(){
while (pq.size() && vis[pq.top().second]) pq.pop();
}
void reset_buffer(){
buffer=0;
buffer_size=0;
}
void optimize(int _u=-1, int _f=-1){
--remain;
int u=-1;
if (_u==-1){
last_value=pq.top().first;
u=pq.top().second; pq.pop();
}else{
last_value=_f;
u=_u; f[u]=_f;
}
vis[u]=1;
for (auto &e:g[u]){
int v=e.first, w=e.second;
if (f[v]>f[u]+w) pq.emplace(f[v]=f[u]+w, v);
}
adjust_pq();
}
}
void InitB(int N, int B, vector<int> S, vector<int> T,
vector<int> D) {
Baijan::n=N;
Baijan::remain=N;
memset(Baijan::f, 0x3f, sizeof Baijan::f);
for (int i=0; i<B; ++i) Baijan::g[S[i]].emplace_back(T[i], D[i]), Baijan::g[T[i]].emplace_back(S[i], D[i]);
Baijan::pq.emplace(Baijan::f[0]=0, 0);
for (int i=1; i<N; ++i) Baijan::pq.emplace(Baijan::f[i]=(1<<20)-1, i);
Baijan::waiting_size=9;
}
void ReceiveB(bool y) {
++Baijan::buffer_size;
Baijan::buffer<<=1; Baijan::buffer|=y;
if (Baijan::buffer_size==Baijan::waiting_size){
if (Baijan::waiting_size==9){
int fa=Baijan::buffer+Baijan::last_value;
if (fa<=Baijan::pq.top().first){
Baijan::FakeSendB(1, 0);
Baijan::waiting_size+=Baijan::ceil_log2();
if (Baijan::ceil_log2()==0){
int v=Baijan::find_node(Baijan::buffer&((1<<Baijan::ceil_log2())-1)), f=(Baijan::buffer>>Baijan::ceil_log2())+Baijan::last_value;
Baijan::optimize(v, f);
Baijan::waiting_size=9;
Baijan::reset_buffer();
}
}else{
Baijan::FakeSendB(1, 1);
Baijan::FakeSendB(9+Baijan::ceil_log2(), (Baijan::pq.top().first==((1<<20)-1)?511:Baijan::pq.top().first-Baijan::last_value)<<Baijan::ceil_log2()|Baijan::find_idx(Baijan::pq.top().second));
if (Baijan::pq.size()) Baijan::optimize();
Baijan::waiting_size=9;
Baijan::reset_buffer();
}
}else{
int v=Baijan::find_node(Baijan::buffer&((1<<Baijan::ceil_log2())-1)), f=(Baijan::buffer>>Baijan::ceil_log2())+Baijan::last_value;
Baijan::optimize(v, f);
Baijan::waiting_size=9;
Baijan::reset_buffer();
}
}
}
