#include "rail.h"
#include <iostream>
#include <vector>
using namespace std;
int d0[5005];
int d1[5005];
int per[5005];
int dist[5005][5005];
void findLocation(int N, int first, int location[], int stype[])
{
int n=N;
int minim=-1,st=0,dr=-1,j,z;
for(int i=0; i<n; i++)
{
for(int j=1; j<n; j++)
{
dist[i][j]=getDistance(i,j);
dist[j][i]=dist[i][j];
}
}
for(int i=0;i<n;i++)
{
per[i]=-1;
for(int j=0;j<n;j++)
{
if((j!=i) && (per[i]==-1 || dist[i][j]<dist[i][per[i]]))
{
per[i]=j;
}
}
}
vector<int>vec;
for(int i=1; i<n; i++)
{
d0[i]=dist[0][i];
if(dr==-1 || d0[i]<d0[dr])
{
dr=i;
}
vec.push_back(i);
}
location[0]=first;
stype[0]=1;
vec.erase(vec.begin()+dr-1);
location[dr]=d0[dr]+first;
stype[dr]=2;
st=0;
for(int i=1; i<n; i++)
{
minim=-1;
for(z=0; z<vec.size(); z++)
{
j=vec[z];
if(dist[st][j]+dist[dr][j]==2*dist[j][per[j]]+dist[st][dr])
{
if(dist[st][j]<dist[st][per[j]] || per[j]==st)
{
location[j]=location[st]+dist[st][j];
stype[j]=2;
}
else
{
location[j]=location[dr]-dist[dr][j];
stype[j]=1;
}
vec.erase(vec.begin()+z);
z=-1;
}
else
{
if(minim==-1 || min(dist[st][j],dist[dr][j])<min(dist[st][minim],dist[dr][minim]))
{
minim=j;
}
}
}
if(minim==-1)
{
break;
}
if(dist[dr][minim]==dist[minim][per[dr]]+dist[dr][per[dr]])
{
location[minim]=location[st]+dist[st][minim];
stype[minim]=2;
dr=minim;
for(int z=0; z<vec.size(); z++)
{
if(vec[z]==minim)
{
vec.erase(vec.begin()+z);
}
}
}
else
{
location[minim]=location[dr]-dist[dr][minim];
stype[minim]=1;
st=minim;
for(int z=0; z<vec.size(); z++)
{
if(vec[z]==minim)
{
vec.erase(vec.begin()+z);
}
}
}
}
}
