#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using idata = vector<int>;
using bdata = vector<bool>;
template<typename T>
using lpq = priority_queue<T, vector<T>, greater<T>>;
using ii = pair<int, int>;
idata distance0;
bdata isD1;
void findLocation(int N, int first, int location[], int stype[])
{
location[0] = first;
stype [0] = 1;
distance0.resize(N, -1);
int minD = 1e9;
int minP = -1;
for (int i = 1; i < N; i ++) {
distance0[i] = getDistance(0, i);
if (distance0[i] >= minD) continue ;
minD = distance0[i];
minP = i;
}
int curDP = minP;
location[curDP] = minD + first;
stype [curDP] = 2;
lpq<ii> queue;
for (int i = 1; i < N; i ++)
if (i != minP)
queue.push({ distance0[i], i });
while (queue.size() != 0) {
const auto nextDP = queue.top(); queue.pop();
int next = nextDP.second;
int off = distance0[curDP] + getDistance(curDP, next);
int res = distance0[next];
if (off == res) continue ;
curDP = next;
location[curDP] = first + distance0[curDP];
stype [curDP] = 2;
}
}
