oh sorry,. i didnt see the graph again before replying. it should be self loop on (5,5) .i misremembered the graph

Yeah, you are right. It is not possible like this Good find.

Though it is still possible to achieve the same results, I will first break (2,5) to make self loop on (2,2) than expand one side to 1 and the other to 8

We break the edge between u and v. In the case I described, we break the edge b/w 2,5 and connect it to 2,6, then 2,7, then 2,1. Its cost becomes — dist[1][5] * 22

Then we take the edge of 2,1 break it to join it to 1,5 then 1,6 then 1,4 then 1,8 Cost becomes dist[2][8] * 22

This is.for case 1, for case 2 also we start by breaking the edge between 2,5 but once the u reaches an intermediate vertex we like we create self loop and expand both sides

1 to u will be — (1,7,6,5) and v to n will be (2,5,6,4,8) The total time become (3+4+1)*22 equal 176

Which is suboptimal so we go for the case 2 and get better answer

Hey, I think there is a typo in tutorial for C. It should be : "Assuming that the central piece is on the light square, we consider 3 cases:"

If you try to find the answer for the sample test case #3 in the D, you will find that the 1st case in the solution is not able to find the correct solution.

In this test case, the correct solution would be to -> take the edge connecting vertex 2, 5 -> connect it to 2, 6 take the now edge connecting vertex 2, 6 -> connect it to 2, 4 take the now edge connecting vertex 2, 4 -> connect it to 4, 4 take the now self loop edge connecting vertex 4, 4 -> connect it to 4, 7 take the now edge connecting 4,7 -> connect it to 4, 1 take the now edge connecting 4, 1 -> connect it to 1, 8

The answer -> (22 * 6 + 22) = 154

So what happened is we saw that the edge connecting the vertex 2, 5 might just be what we need for the best possible path but if we try the case 1 that we thought of then the total time won't be the shortest possible we could get. We could instead just take one of the vertex and connect it an intermediate vertex ( a vertex that is present in the shortest path from 1 to n). After this, we create a self loop on this intermediate vertex. (Total time up till now -> dist[u][x] + 1

Now we can just expand this self loop on both sides -> dist[x][1] + dist[x][n]

Now one last time of actually travelling this edge -> 1

total time => (dist[u][x] + 1 + dist[x][1] + dist[x][n] + 1 ) * w

shows me error "cannot read property 'length' of undefined" when trying to expand the 'future'/'running'/'past' column in contest does not show anything in the problems box gave the handle in settings but only shows "handle:shashwatgandhi88" nothing else like in the image