#include "rail.h"
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <utility>
using namespace std;
priority_queue < pair < pair < int , int > , pair < int , int > > , vector < pair < pair < int , int > , pair < int , int > > > , greater < pair < pair < int , int > , pair < int , int > > > > all;
int dis[5005][5005]={0};
bool have[5005];
void findLocation(int N, int first, int location[], int stype[])
{
int x,y,z,i,j;
location[0]=first;
stype[0]=1;
all.push(make_pair(make_pair(0,0),make_pair(0,-1)));
for(i=0;i<N;i++) for(j=0;j<N;j++) dis[i][j]=getDistance(i,j);
while(!all.empty())
{
y=all.top().first.first;
x=all.top().second.first;
z=all.top().second.second;
all.pop();
if(have[x]) continue;
have[x]=1;
//printf("%d %d %d\n",x,y,z);
if(z!=-1)
{
//printf("aa %d %d\n",x,z);
if(stype[z]==1)
{
stype[x]=2;
location[x]=location[z]+dis[z][x];
}
else
{
stype[x]=1;
location[x]=location[z]-dis[z][x];
}
}
for(i=0;i<N;i++) all.push(make_pair(make_pair(y+dis[x][i],dis[x][i]),make_pair(i,x)));
}
}
