I was the solving the INOI problem free ticket. When I submit it, it gives wrong answer for larger values and correct answer for smaller values. I am unable to figure out why. Can anyone help me figure out. Here is my code.
From what I can see you are Simulating the process using a Recursive routine. Use the floyd warshall algorithm for pairwise shortest path \theta(n^3)
This is a standard Floyd-Warshall problem . Here is the way to do it with floyd-warshall.
you can simply use the Floyd-Warshall algorithm on the whole graph, or an iterative Djikstra (Djikstra from each node).
you can check the complexity of both in different cases from this thread:
If you need to take sneak-peak at my code, and then try it yourself, here is my code using iterative Djikstra->
Another question, does he start ever from 1 or can start from some other places?