Project Code 2.0 TIMET Problem

Please share your approach for this problem of Project Code 2.0:

https://www.codechef.com/PROC2020/problems/TIMET

1 Like

Floyd-Warshall

2 Likes

Just check whether there is any negative cycle in the graph. If so, it is always possible else not possible to go 10 yrs past in time.
Negative cycle can be found using Bellman Ford or Floyd Warshall.

1 Like

Can Someone tell me why i am getting TLE on Task#4?
Submission Link : https://www.codechef.com/viewsolution/34927070

1 Like

Line 22 : Replace n * n - 1 with (n - 1)
You are doing way extra iterations. Follow the algorithm.

1 Like

Thanks.

apply bellman ford for 1st node because he always start at city 1 and try to find a negative cycle, if exist print YES else NO

The values in the matrix are in MINUTES

As @phoenix_307 said, the values in the grid are in minutes. So without a cycle you can go only 100 minutes in past.

Dumb me. Thank you.