There are [N] locations in a town labeled 1....N. You are provided a list of streets S (|S| = M) where a single street connects two locations in the town and has an associated distance. You also provided a list H of houses in the town and a list C, all the COVID-19 testing centers in the town. For each house find the shortest distance to the closest testing center. Solve the problem in O(M * log N) time.
I see that this is a graph problem and I can build an undirected graph from the list of streets because a street can be viewed as an edge where the edge-weight is the distance between the two locations.
Because the problem wanted to find the shortest distance to a testing center for all houses my thought was to run Dijkstra's algorithm for each house in H. However, this would give me a runtime of O(|H|*MlogN) and we want a runtime of O(MlognN). Are there any modifications that can be made to Dijkstra's algorithm to achieve this runtime? I have to treat each house as a source vertex to find the shortest distance and I don't see any way that can be done in the required time complexity.
Use Dijkstra initialized from each center, not house.
Mark all houses as unvisited, mark all centers with distance 0
Add all centers to PQ.
Continue with dijkstra...