I was trying to solve this problem , at the beginning i thought that the train track should pass by each city, so this can be solved in O(n^2 * log(n) ) with brute force, but after reading carefully i found that The citizens of a city can use the train line if the track goes 1 km or closer to the city center.

How to solve this shit, i have no idea ?