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 if we imagine there is no negative edge and nodes then there will be two cases we have to handle, case 1: We can stay in the city case 2: We can go just adjacent city
as all values are positive so there is no meaning to go further after adjacent cities.
This can help you.
I think going through a city does not mean entering the city.
A counter case for Case 2 would be :
n = 4, m = 3
val_to_enter = {1000, 500, 1, 4}
edges :
1 2 2
2 3 1
3 4 1
now for city 1 according to you the answer would have had been = 502(entering city 2) .
Instead a optimal way would have had been to enter city 3 with cost = 6.
