#include "rail.h"
#include<iostream>
#include<set>
using namespace std;
const int N = 5055;
const int inf = 1e9;
int d[N][N];
int q[N];
int n;
int used[N];
void findLocation(int N, int first, int location[], int stype[]) {
n = N;
for (int i = 0 ; i < n ; ++ i) {
for (int j = 0 ; j < i ; ++ j) {
d[i][j] = d[j][i] = getDistance(i, j);
}
}
for (int i = 0 ; i < n ; ++ i) {
q[i] = inf;
}
q[0] = 0;
set<pair<int,int>>st;
st.insert({0, 0});
stype[0] = 1;
location[0] = first;
while (st.size()) {
int v = st.begin()->second;
st.erase(st.begin());
used[v] = 1;
for (int i = 0 ; i < n ; ++ i) {
if (used[i]) continue;
if (q[i] > d[i][v]) {
st.erase({q[i], i});
q[i] = d[i][v];
stype[i] = 3 - stype[v];
if (stype[v] == 1) location[i] = location[v] + d[i][v];
else location[i] = location[v] - d[i][v];
st.insert({q[i], i});
}
}
}
}
