INOI Problem Help

general
,
1

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.

http://ideone.com/e.js/LeqzkY

2

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)

3

This is a standard Floyd-Warshall problem . Here is the way to do it with floyd-warshall.

2 Likes
4

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:
StackOverflow-DjikstraVsFloydWarshall.

If you need to take sneak-peak at my code, and then try it yourself, here is my code using iterative Djikstra->

Ideone-iaKU8P

5

Another question, does he start ever from 1 or can start from some other places?