#include "rail.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
using namespace std;
vector<vector<int> > distances;
int gdistance(int i, int j){
if (i == j){
distances[i][i] = 0;
}
if (distances[i][j] == -1){
distances[i][j] = getDistance(i, j);
distances[j][i] = distances[i][j];
}
return distances[i][j];
}
void findLocation(int N, int first, int location[], int stype[])
{
distances = vector<vector<int> > (N, vector<int> (N, -1));
for (int i = 0; i < N; i++){
location[i] = -1;
stype[i] = -1;
}
stype[0] = 1;
location[0] = first;
vector<int> d0 (N, -1);
d0[0] = 0;
for (int i = 1; i < N; i++){
d0[i] = gdistance(0, i);
}
int x = distance(d0.begin(), min_element(++d0.begin(), d0.end()));
location[x] = location[0] + d0[x];
stype[x] = 2;
for (int i = 0; i < N; i++){
if (i != 0 && i != x){
if (gdistance(0, i) == gdistance(x, i) + gdistance(0, x)){
stype[i] = 1;
location[i] = location[x] - gdistance(i, x);
} else {
stype[i] = 2;
location[i] = location[0] + gdistance(0, i);
}
//cout << i << ' ' << location[i] << ' ' << stype[i] << endl;
}
}
}
