I have tried [Free ticket][1] Problem…But got 30/100 points…How to get 100/100

This is my

```
[2] . Please help me.
[1]: https://www.codechef.com/IOIPRAC/problems/INOI1402
[2]: http://ideone.com/IoknMd
```

I have tried [Free ticket][1] Problem…But got 30/100 points…How to get 100/100

This is my

```
[2] . Please help me.
[1]: https://www.codechef.com/IOIPRAC/problems/INOI1402
[2]: http://ideone.com/IoknMd
```

From what I understand, what you seem to be doing is that you are simply printing the cheapest cost of the route from 1 to N. What the question asks is that **you must print the maximum cost among the cheapest routes between all pair of cities.** That is, in the sample test case, (assume (u,v) denotes cost of cheapest route between u and v) you must compute (1,2),(1,3),(1,4),(2,3),(2,4) and (3,4) and find the maximum among all these costs.

I believe a suitable algorithm for this question will be [Floyd Warshall Algorithm][1]. You can refer to http://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/ to know more.

Because of constraints you can solve directly using Dijkstra as well. You will just have to select u (source) and v(destination) each time. This approach is not efficient enough, though. I can share the corrected code, but since it is technically part of an ‘ongoing contest’ it would be better if you try out the implementation on your own.

Edit: You don’t even need to select the destination each time for Dijkstra. Just select source node, and use Dijkstra until your priority_queue is empty. The nature of Dijkstra using priority queue will allow you to get the shortest distances of all nodes from source node, without choosing a specific destination node (destination node is only useful to terminate the while() loop early. Not needed here). After that store all these results and finally print maximum of all the results. Again, source node varies from 1 to N.

Edit 2: My bad. It should have been Floyd-Warshall and not Bellman Ford. Corrected it.

Edit 3: You can refer to my 100 points code. http://ideone.com/cp0xEt Again, it isn’t as efficient as the one that you can get using Floyd Warshall.

[1]: https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm

1 Like

Please tell me -What is the wrong in this code?

It is practice contest…

links :

I told you. The mistake here is that you are only finding the minimum cost between node 1 and N. What the question says is that find the minimum cost between all the pairs u and v, 1 <= u < v <= N and then take the maximum of all those costs.

1 Like

I have added a link to my code. You may refer to it.

My code is 30/100…

This time, you are only starting from node 1 and checking distances of all nodes from 1. You have to start from all nodes, not just 1. So I simply generalized your Dijkstra function for all values of ‘start’ from i=1 to n, and I take the maximum of all the values ‘mx’ thrown by your function.

So you see, I have made a really minor change. Look at http://ideone.com/ZWbXiZ

Works beautifully. 0.07s and 100 pts. Much better than my code (took ~1.3s!) I will have to check where did I go wrong in my code

So you see, you were on the right path, but the solution was incomplete!

Happy learning!