#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3;
const int inf = 1e9;
int memo[maxn][maxn];
int get(int i, int j){
if(i == j) return 0;
if(memo[i][j] != -1){
return memo[i][j];
}
return memo[i][j] = memo[j][i] = getDistance(i, j);
}
void findLocation(int n, int first, int location[], int stype[])
{
for(int i = 0; i < n; i ++){
location[i] = -1;
for(int j = 0; j < n; j ++){
memo[i][j] = -1;
}
}
location[0] = first;
stype[0] = 1;
if(n == 1){
return;
}
int cl = inf + 1, ind = 0;
for(int j = 1; j < n; j ++){
if(cl > get(0, j)){
cl = get(0, j);
ind = j;
}
}
int far = first, f = 0;
for(int j = 1; j < n; j ++){
if(ind == j){
location[j] = first + cl;
stype[j] = 2;
}else
if(get(0, j) == cl + get(ind, j)){
location[j] = first + cl - get(ind, j);
stype[j] = 1;
}
if(stype[j] == 1 && far < location[j]){
far = location[j];
f = j;
}
}
// cout << far << ' ' << f << endl;
for(int i = 1; i < n; i ++){
if(location[i] != -1) continue;
if(first + cl - far + get(f, i) == get(ind, i)){
location[i] = far + get(f, i);
stype[i] = 2;
}
}
}
