Fire stations
A city has n crossings, m two-way streets of known length and k fire stations, each at its own crossing. The city wants to know how far every crossing is from the nearest station by road: that distance turns almost directly into the time a fire engine needs to arrive.
For every crossing, print the distance to the nearest fire station. In one of the tests this is the real Almaty, but the stations are put at random places—do not look for the addresses of real fire stations in the answer.
Input
The first line holds n, m, k (1 ≤ n ≤ 50,000, 0 ≤ m ≤ 100,000, 1 ≤ k ≤ n). Then m lines a b w—a street w long (1 ≤ w ≤ 10,000). The last line holds the k crossings with fire stations; numbers may repeat.
Output
One line of n numbers separated by spaces: for crossing v = 1, 2, …, n, the distance to the nearest station, or -1 if no station can be reached.
Examples
Example 1
7 8 2 1 2 4 2 3 3 3 4 5 4 5 2 5 6 6 6 7 1 2 6 10 3 7 8 1 5
0 4 7 2 0 6 7
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
You could run Dijkstra from every station and take the minimum. How much would that cost with two thousand stations and fifty thousand crossings?
2Hint 2
Imagine that all stations are joined to one imaginary crossing by streets of zero length. What does the shortest distance from that imaginary crossing mean then?
3The idea
Add a fictitious source vertex and join it to every station with edges of length 0. The distance from the source to v is exactly the distance from v to the nearest station. So one run of Dijkstra is enough. The fictitious vertex need not even exist: its only step is to put every station on the heap with distance 0. This is called a multi-source search.
4Walkthrough
Read the graph. For every station set dist[s] = 0 and push it onto the heap (skip repeats). Then the usual Dijkstra until the heap is empty, with no early exit: the answer is needed for every vertex. Vertices never reached are printed as −1.
The wave now starts from all the stations at once and grows around each of them simultaneously. A crossing goes to the station whose wave reached it first—the nearest one. You can also record which station it was: that is how a city is split into areas of responsibility, the road version of a Voronoi diagram.
4+Solution
5Complexity
One pass of Dijkstra: O((n + m) log n) whatever the number of stations. A separate run from every station would cost k times more—with k = 2000, the difference between a fraction of a second and an hour.
6Common mistakes
- Dijkstra from every station. The answers are right, but the test with two thousand stations runs out of time.
- A search from every crossing to the stations. Even worse: n runs instead of k.
- An early exit. In the problem with one finish we stopped once the finish was popped. Here there is no finish—every distance is needed.
- Repeated stations. If a number appears twice, nothing breaks, but do not push it onto the heap two hundred times—that is wasted work.