#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
const int maxN = 5005;
int dist[maxN][maxN];
int query(int x, int y) {
if (dist[x][y] != -1) {
return dist[x][y];
}
int val = getDistance(x, y);
dist[x][y] = val;
dist[y][x] = val;
return val;
}
void findLocation(int N, int first, int location[], int stype[])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dist[i][j] = -1;
}
}
for (int i = 0; i < N; i++) {
dist[i][i] = 0;
}
location[0] = first;
stype[0] = 1;
int best = -1;
for (int i = 1; i < N; i++) {
if (best == -1 || query(0, i) < query(0, best)) {
best = i;
}
}
location[best] = first + query(0, best);
stype[best] = 2;
for (int i = 1; i < N; i++) {
if (i == best) {
continue;
}
int d = query(i, best);
int d2 = query(0, i);
if (d2 == d + dist[0][best]) { // LEFT
location[i] = location[best] - d;
stype[i] = 1;
} else if (d == d2 + dist[0][best]) { // RIGHT
location[i] = location[0] + d2;
stype[i] = 2;
} else {
exit(-1);
}
}
}
