N cities are connected using bidirectional roads (there may be multiple roads between two cities and the graph may not be fully connected).
There is a value associated with each nodes ($$$A[i]$$$) and with each edges. The cost of entering a city is $$$A[i]$$$.
We have to find the minimum cost of entering any city starting from every possible element $$$i$$$.
Example : 4 cities having value (5, 7, 100, 11) and roads are (u, v, w) where (u, v) are nodes and w is the weight of the edge.
(1, 2, 5), (3, 4, 50)
Answer is (5, 7, 61, 11)
Explanation : starting from 1 we can enter city 1 (cost 5)
starting from 2 we can enter city 2 (cost 7)
starting from 3 we can enter city 4 (cost: (3 -> 4)edge + value_of_entering_4(11) = 61)
starting from 4 we can enter city 4 (cost: 11)
Constraints: All the edge values and cost of entering a city is $$$<= 10^9$$$ Number of cities and number of roads $$$<= 10^5$$$
Let's approach it backwards: what's the cost to get to node x starting from any city?
If we model the cities as edges with weight = their entry cost from a source node to the city location, this is just Dijkstra's algorithm.
The optimal answer for each node will be even itself or one of its adjacent nodes. since the answer will get bigger if we lengthen the path.
Just have a look here
it must be said that when passing through a node we don't enter it.
In the sample case itself while going from 3 -> 4 we don't add the node value of 3!
The starting node doesn't count (As I understood it).
The following might work (the idea is similar to Dijkstra's shortest path algorithm):
Maintain a min heap containing pairs $$$(u, z)$$$ where $$$u$$$ is the vertex number and $$$z$$$ is the current answer for that vertex. Initially insert all $$$(i, A[i])$$$ into the min heap where $$$A[i]$$$ is the cost of entering the vertex $$$i$$$. The min heap is ordered by the $$$z$$$ value.
Also maintain an array $$$ans$$$ which is initially same as $$$A$$$.
Keep on extracting $$$(u, z)$$$ from the min heap. If $$$z > ans[u]$$$ you do nothing and continue. Else for each $$$v$$$ which is adjacent to $$$u$$$ if $$$ans[v] > (ans[u] + cost(u, v))$$$ you set $$$ans[v] = ans[u] + cost(u, v)$$$ and insert $$$(v, ans[v])$$$ into the min heap.
The $$$ans$$$ array should contain the desired result.
I don't get a counter case but can you please proof correctness or give some intuition behind it's correctness?
It is not difficult to see that you will directly enter the city which has the least cost to enter out of all the cities. So for the city that has the least cost to enter, the answer is the cost of entering that city itself. Now this city can help you minimize the answer for its adjacent cities. So you try to minimize the cost of its neighbours. Once you have found the answer for the first city (the one which has the smallest cost to enter), you look for the next city. Again you will greedily pick the city which now has the least cost to enter. So at each moment, you are making a greedy choice and proceed in the same manner as described.
The main point is that you start with the city that has the smallest cost to enter(since you can in no way minimize its answer if there are positive weights) and from that you can develop an intuition for the idea.
Try to relate this to how Dijkstra works. Maybe that will help.