#include "towns.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define pii pair<int, int> #define fi first #define se second int hubDistance(int n, int sub){ vector<int> dist(n, 0), dista(n, 0), distb(n, 0); for (int i=1; i<n; ++i)dist[i]=getDistance(0, i); int mx=-1, a=-1, b=-1, ans=INT_MAX/2; for (int i=0; i<n; ++i)if (dist[i]>mx)mx=dist[i], a=i; for (int i=0; i<n; ++i)if (i!=a)dista[i]=getDistance(a, i); mx=-1; for (int i=0; i<n; ++i)if (dista[i]>mx)mx=dista[i], b=i; for (int i=0; i<n; ++i)if (i!=b)distb[i]=getDistance(b, i); for (int i=0; i<n; ++i)ans=min(ans, max(dista[i]-(dista[i]+distb[i]-dista[b])/2, distb[i]-(dista[i]+distb[i]-dista[b])/2)); return ans; }