INOI freeticket

Hi,
I am using floyd warshall algo for this problem but still only 50% test cases are passed. Could anyone please suggest?

problem: https://www.codechef.com/INOIPRAC/problems/INOI1402
my solution : https://www.codechef.com/viewsolution/27517058

Any hints will be appreciated.