There are N cities and M bidirectional roads. Each road has a particular cost to travel on.
K cities among these have corona testing facility for a particular amount (different cities may have different prices for testing).
Determine for each city, the minimum cost to travel to any corona testing facility and get tested.
Model the problem as a weighted graph with N+1 nodes. Draw an edge between node 0 and node i with a corona testing facility (for all i), and give it weight C_i.
Now, we have reduced the problem to finding the shortest path from each city to node 0. This is equivalent to finding the shortest path from node 0 to each city, which is a classical Dijkstra problem!
Dijkstra (with minimum priority queue) takes
which is the time complexity per test case.
Editorialist’s solution can be found here.
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)