#include "Azer.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace Azer{
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))
#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple
#define tcT template<class T
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) for(int i = 0; i < (r); ++i)
#define FORD(i, l, r) for(int i = (l) - 1; i >= (r); --i)
tcT> bool minimize(T& a, const T& b){
return (a > b ? a = b, 1 : 0);
}
tcT> bool maximize(T& a, const T& b){
return (a < b ? a = b, 1 : 0);
}
tcT> using min_heap = priority_queue<T, vector<T>, greater<T>>;
tcT> using max_heap = priority_queue<T>;
using ll = long long;
using db = double;
using ull = unsigned long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;
const int MAX = 2e3 + 5;
int N, M, T, c, LOG_N, LOG_500, stateA, stateB, minA, num, remainBits, type, dist[MAX], vis[MAX];
vpi adj[MAX];
/*
Estimation and Notes
- max LOG_N = 11 Bits
- LOG_500 = 9 Bits
- type = 1 : Delta
- type = 2 : index
*/
int findCandidate(){
int res = -1;
F0R(i, N) if(!vis[i]){
if(res == -1 || dist[i] < dist[res]){
res = i;
}
}
return res;
}
void sendDist(int d){
for(int i = LOG_500; i >= 0; --i){
SendA(d >> i & 1);
}
num = 0;
remainBits = LOG_500 + 1;
type = 1;
}
void sendIndex(int id){
for(int i = LOG_N; i >= 0; --i){
SendA(id >> i & 1);
}
num = 0;
remainBits = LOG_N + 1;
type = 2;
}
void relax(int u){
// cerr << "Azer relax " << u << " | " << dist[u] << '\n';
stateA = stateB = dist[u];
vis[u] = 1;
for(auto [v, w] : adj[u]){
minimize(dist[v], dist[u] + w);
}
++T;
if(T == N) return;
c = findCandidate();
int gap = min(503, dist[c] - dist[u]); //instead of storing the whole dist, we just need to store the \Delta
minA = dist[c];
// cerr << "Azer send " << gap << ", candidate = " << c << '\n';
sendDist(gap);
}
} // namespace
using namespace Azer;
void InitA(int N, int M, vector<int> U, vector<int> V, vector<int> C) {
::N = N;
F0R(i, M){
int u = U[i], v = V[i], w = C[i];
adj[u].eb(v, w);
adj[v].eb(u, w);
}
memset(dist, 0x3f, sizeof(dist));
LOG_N = 31 - __builtin_clz(N - 1);
LOG_500 = 31 - __builtin_clz(500);
dist[0] = 0;
relax(0);
}
void ReceiveA(bool x) {
num = 2 * num + x;
--remainBits;
assert(remainBits >= 0);
if(remainBits == 0){
// cerr << "Azer : " << "num = " << num << ", type = " << type << '\n';
if(type == 1){
stateB += num;
if(minA <= stateB){
stateB = minA;
sendIndex(c);
relax(c);
} else{ //start receive the index
num = 0;
remainBits = LOG_N + 1;
type = 2;
}
} else{
assert(minA > stateB);
dist[num] = stateB;
relax(num);
}
num = 0;
}
}
std::vector<int> Answer() {
vi ans(dist, dist + N);
return ans;
}
#include "Baijan.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace Baijan{
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))
#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple
#define tcT template<class T
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) for(int i = 0; i < (r); ++i)
#define FORD(i, l, r) for(int i = (l) - 1; i >= (r); --i)
tcT> bool minimize(T& a, const T& b){
return (a > b ? a = b, 1 : 0);
}
tcT> bool maximize(T& a, const T& b){
return (a < b ? a = b, 1 : 0);
}
tcT> using min_heap = priority_queue<T, vector<T>, greater<T>>;
tcT> using max_heap = priority_queue<T>;
using ll = long long;
using db = double;
using ull = unsigned long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;
const int MAX = 2e3 + 5;
int N, M, T, c, LOG_N, LOG_500, stateA, stateB, num, minB, remainBits, type, dist[MAX], vis[MAX];
vpi adj[MAX];
/*
Estimation and Notes
- max LOG_N = 11 Bits
- LOG_500 = 9 Bits
- type = 1 : Delta
- type = 2 : index
*/
int findCandidate(){
int res = -1;
F0R(i, N) if(!vis[i]){
if(res == -1 || dist[i] < dist[res]){
res = i;
}
}
return res;
}
void sendDist(int d){
for(int i = LOG_500; i >= 0; --i){
SendB(d >> i & 1);
}
num = 0;
remainBits = LOG_500 + 1;
type = 1;
}
void sendIndex(int id){
for(int i = LOG_N; i >= 0; --i){
SendB(id >> i & 1);
}
num = 0;
remainBits = LOG_N + 1;
type = 2;
}
void relax(int u){
// cerr << "Baijan relax " << u << " | " << dist[u] << '\n';
stateA = stateB = dist[u];
vis[u] = 1;
for(auto [v, w] : adj[u]){
minimize(dist[v], dist[u] + w);
}
++T;
if(T == N) return;
c = findCandidate();
int gap = min(503, dist[c] - dist[u]); //instead of storing the whole dist, we just need to store the \Delta
minB = dist[c];
// cerr << "Baijan send " << gap << ", candidate = " << c << '\n';
sendDist(gap);
}
} // namespace
using namespace Baijan;
void InitB(int N, int M, vector<int> U, vector<int> V, vector<int> C) {
::N = N;
F0R(i, M){
int u = U[i], v = V[i], w = C[i];
adj[u].eb(v, w);
adj[v].eb(u, w);
}
memset(dist, 0x3f, sizeof(dist));
LOG_N = 31 - __builtin_clz(N - 1);
LOG_500 = 31 - __builtin_clz(500);
dist[0] = 0;
relax(0);
}
void ReceiveB(bool x) {
num = 2 * num + x;
--remainBits;
assert(remainBits >= 0);
if(remainBits == 0){
// cerr << "Baijan : " << "num = " << num << ", type = " << type << '\n';
if(type == 1){
stateA += num;
if(minB < stateA){
stateA = minB;
sendIndex(c);
relax(c);
} else{ //start receive the index
num = 0;
remainBits = LOG_N + 1;
type = 2;
}
} else{
assert(minB >= stateA);
dist[num] = stateA;
relax(num);
}
num = 0;
}
}
