TeleportsNetwork topcoder SRM409 div2 level3
Introduction If you have not tried to solve this problem by yourself, please do so. Otherwise, this post will make little sense to you.
Solution to this problem is straightforward, which can be broke down into two parts:
construct the graph; find the min-max inconvenience. Part-I: Graph Construction Let $G(V,E)$ be the graph, and we know the order of $G$ is $\vert V\vert = n$. Because each city, except the capital, is going to build one road, the total number of edges is $\vert E\vert = m = n-1$. The rule of building a road from a city $i$ can be restated as “find the closest city $j$, ${\arg\min}_{j\in V,\ j\neq i} d(i,j)$, such that $d(0,j) < d(0,i)$”, where $d(\cdot)$ is the Euclidean distance between two cities. If the situation is degenerate, use $x$ and $y$ coordinates to resolve it. This is done in the function of build_road().
