#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=5e3+5;
int dp[nx][nx], mn[nx], vs[nx];
int query(int i, int j)
{
if (i>j) swap(i, j);
if (dp[i][j]!=0) return dp[i][j];
return dp[i][j]=getDistance(i, j);
}
void findLocation(int N, int first, int location[], int stype[])
{
location[0]=first;
stype[0]=1;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, 0});
for (int i=1; i<N; i++) mn[i]=1e9;
while (!pq.empty())
{
auto [w, u]=pq.top();
pq.pop();
if (vs[u]) continue;
vs[u]=1;
for (int v=0; v<N; v++) if (v!=u&&mn[v]>query(u, v)) mn[v]=query(u, v), stype[v]=2-stype[u]+1, location[v]=(stype[u]==1)?location[u]+query(u, v):location[u]-query(u, v), pq.push({query(u, v), v});
}
//for (int i=0; i<N; i++) cout<<"debug "<<i<<' '<<stype[i]<<' '<<location[i]<<'\n';
}
