Help in a graph question

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

2 Likes

@l_returns
@aryanc403
Can you share your ideas on this problem??

1 Like

if there is cycle of length 3 can i go 1->2->3->1 or i can visit a vertex only one time when starting from vertex V ?

Doing so will not give any benifit I think.

Still such paths are allowed here too.

it can give benifit, like all edge weight and Ai is negative

Can you give the solution approach if there are no negative edges and values?

That will also be very much helpful!

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.

I think it will fail as entering a city will have a totally different cost.

@pk301, you can post this question on CF . I too am excited to know the solution to this problem

@aman_robotics Thanku for suggestion.
Please upvote this question here.

@aman_robotics will I get notification in CF also when anyone answers?

Yes, I guess you would get as a mail :slight_smile:

opps, overlooked that.