I was trying this problem, but cannot properly understand the problem statement.
More explicitly, this statement- " all n cities of Berland were connected by n two-way roads in the ring, i. e. each city was connected directly to exactly two other cities, and from each city it was possible to get to any other city. Government of Berland introduced one-way traffic on all n roads,"
Also, can anyone explain the sample test case 1 and 2
The question asks what will be the minimum cost to redirect (change the direction of) road/s so that there is a path between any pair of cities. See sample test 1 in the photo. The only road you need to change the direction of will be 1-2. Since its redirecting cost is 1, so the answer is 1.
Please inform in case of confusion.
Okay, so for 2nd test case, path was from 1–>2, 1–>3 and 3–>2. To make it a cycle,with min cost, we are reversing the array of 2—>3 and 1–>3 right, so min cost is 2
Exactly…and not the one whose cost is 5.
Yes understood perfectly. Thanks bro
No problem👍
