A town has intersections 0 .. n-1 joined by two-way streets; streets is a list of (a, b, minutes). Tonight only a few pharmacies are open, standing at the intersections listed in open_at.
For every intersection, a resident wants to know how many minutes it takes to walk to whichever open pharmacy is closest.
Implement nearest_pharmacy(n, streets, open_at) -> list[int]: element v is the shortest walking time from v to any intersection in open_at (0 if v itself has one), or -1 if no open pharmacy can be reached.
streets = [(0, 1, 4), (1, 2, 1), (2, 3, 6), (3, 4, 2), (1, 4, 10)]
nearest_pharmacy(6, streets, [0, 3])
# [0, 4, 5, 0, 2, -1] node 2: via 1 to 0 is 5, direct to 3 is 6; node 5 is isolated
Constraints: 1 <= n <= 10^5, up to 2 * 10^5 streets, 1 <= minutes <= 10^4, open_at may be empty or repeat an intersection. Running a separate Dijkstra from every pharmacy (or from every intersection) is too slow when there are many pharmacies.
Show hint
run one Dijkstra with every pharmacy already on the heap at distance 0; the first time a node is settled, its distance is to the nearest one.