Chef likes to play with graphs a lot. Today he created a graph in the following way. He first lays down N nodes in a circle. The nodes nodes are numbered from 1 to N , in the clockwise order, i.e. the node 2 is followed by 1, 3 is followed by 2, and 1 is followed by N . There is an edge between each adjacent pair of vertices, so there are total N such edges. Each edge has an integer associated with it (may be negative).

we will be given start and end then we have to find minimum cost for going from start to end

link:https://www.codechef.com/problems/CHEFCRUN

Input: 5

-5 100 100 100 2

1 5

Output:

-8

Explanation Chef goes from 1 to 2 by incurring a cost of -5. Then from 2 to 1 using the edge second time and incurring cost of -5 again. Now, he can not use the edge between 1 and 2 again, as he has traversed the edge already twice. Now he will go from node 1 to node 4 by paying a cost of 2. Total sum of costs incurred is -5 + -5 + 2 = -8. This is the minimum possible cost that Chef can have

Imagine that all of the edges are stored in

arr(the weight of the edge is stored). Create an array with size N in order to keep the prefix-sum. Then do this:int sum = 0;

for (int i = 0; i < n; i++) {

sum += arr[i];

preSum[i] = sum;

}

TotalSumis the sum of all the edges' weights.randlare the nodes that we want to find the path between.I hope it helped.

Remember, it is not a complete solution but the main idea is the same...

well there is one more condition here since the edges can be negative weighted and also we can visit each edge twice then we can simply traverse the edge back and forth so we add (2*weight) to our ans,in case the edge weight is negative our ans gets reduced by (2weight)

Yes, as you said it is easy to handle it when we have negative edges and we can visit them twice. Just multiply negative values by 2.

Auto comment: topic has been updated by rprudhvi590 (previous revision, new revision, compare).Auto comment: topic has been updated by rprudhvi590 (previous revision, new revision, compare).