#include <bits/stdc++.h>
#include "rail.h"
#define MAX 5010
#define ff first
#define ss second
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
int k, f;
int dist[MAX][MAX];
bool marc[MAX];
vector<pair<int,pii> > erase;
set<pair<int,pii> > s;
set<pair<int,pii> >::iterator it;
void add(int d, int i, int j) { s.insert(mp(d , mp(i , j))); }
void findLocation(int n, int first, int location[], int stype[])
{
for(int g = 0 ; g < n ; g++)
for(int h = g + 1 ; h < n ; h++)
dist[g][h] = dist[h][g] = getDistance(g , h);
for(int g = 1 ; g < n ; g++) add(dist[0][g] , 0 , g);
marc[0] = true;
stype[0] = 1;
location[0] = first;
while(!s.empty())
{
it = s.begin();
int d = it->ff;
int i = it->ss.ff;
int j = it->ss.ss;
if(marc[j])
{
s.erase(it);
continue;
}
marc[j] = true;
stype[j] = 3 - stype[i];
location[j] = location[i] + ((stype[i] == 1) ? (d - 1) : (-d + 1));
for(int h = 0 ; h < n ; h++) if(!marc[h]) add(dist[h][j] , j , h);
}
}
