Hi everyone. I've been practicing on the INOI server lately, however I've not yet solved even a single question. I studied Graph Theory for the first time last week and decided to do the FREETICKET problem using Djikstra's Algorithm (here). I've tried to solve the problem innumerable times, but am still not able to do so. If someone could please tell me the pseudocode, it'll be of great help. I'm asking for the pseudo code as I program in Java and am sometimes not able to understand c++ syntax. Also, if you could review my pseudo code once, I'll be very grateful.
I realize this is a tedious work but please help me, it's really important. Thank you all for your help, guys. Note: when I'm trying the sample case, it returns maximum int value, which means the relaxation is not being done properly. asked 04 Jan '15, 00:47

Hi! Firstly, I hope you understand the motivation behind Dijkstra's algorithm. It's good to look through the proof (so you know why negative edges can't be handled), but just a understanding behind the motivation is enough for tackling simple problems. Imagine you put some water at the first node, and let it flow. Each edge's cost is represented by its length. Now, at each iteration of the main loop in Dijkstra's algorithm, you mark the node which the water would touch next. Try drawing this on a whiteboard or piece of paper, visualizing the water flowing through. Secondly, in plaintext, the solution of the "freeticket" problem is as followsfor each node, you find the farthest node that can be reached by starting from it. For all such "farthest nodes", you take the most costly one. It is like putting water in each node, one at a time, and marking the node where it reaches last. You do this for every node, and then take a maximum over all such values.
Where Here's a simple solution in C, which I've hacked together with comments so the syntax isn't an issue:
Lastly, your code. I didn't take a deep look, but if I'm not wrong, for each node, you're just marking the maximum "first flight" it could take. EDIT: Oops. Forgot some motivation jumbo mumbo. If everyone solved all problems in their first go, surely they'd be no need for competitions to motivate us to learn more? It's okay. You'll soon solve one. Then another. Then all. What's important is to enjoy the process, to struggle through the problem while you canand most importantly, to know when's the right time to give up and ask on CodeChef! :) Hope I could help, Cheers. answered 04 Jan '15, 01:47
@vikramnitin9  only used Dijkstra's because the OP asked for it! :)
(04 Jan '15, 19:41)
@idraumr Thanks a lot mate, I understand how much effort you put into writing this answer, and I really thank you for that. However, I adapted your code as it is into java because I really couldn't figure it out myself, even after using FloydWarshall, but even then there seems to be some problem.
(05 Jan '15, 21:34)
@idraumr If you don't mind, can you post a complete solution, with all the input and output like asked in the question (incase you're busy, please don't waste your time by typing this. If not possible, maybe you can look at my code and check the problem in this,it is a direct copy of your code, above, BTW: http://pastebin.com/rQt8gUXx ).
(05 Jan '15, 21:36)
@pm1511  http://pastebin.com/0f06pH4e, there you go. I get 100/100 on the grader.
(05 Jan '15, 22:10)
@idraumr Thanks a ton, bro. Incidentally, I'd solved the problem just a few minutes before you posted your code. But once again, I cannot express how much gratitude I owe you for your great effort in helping a fellow coder. Hope you clear INOI (if you're appearing, or ICPC, in case you're in college) :D
(05 Jan '15, 23:42)
@pm1511  I'm an INOI participant myself. All the best to you too!
(06 Jan '15, 13:18)
@idraumr I've always had some kind of fear of such graph problems which involve Shortest path algorithms, never have I seen such a simple implementation of the Dijkstra. Thank you so much for taking the pain to comment out every little detail in your code! A code speaks a thousand words! This is the first problem I have attempted using Dijkstra's algorithm and I now feel more confident :) Just a question, when should we use heaps to implement Dijkstra's algorithm?
(10 Jan '15, 16:18)
1
If N is the number of vertices, and M is the number of edges in the graph, heap based Dijkstra runs in O(MlogN), whereas the regular implementation runs in O(N^2). So if the N^2 is too big to run in the time limit, and M is much smaller, then heapbased will work. For example, consider if N <= 10^5, M <= 10^5 (most graph problems with large N seem to have constraints like this). Then clearly N^2 is too big but MlogN works. You can try this problem to test your heapbased dijkstra implementation: http://codeforces.com/problemset/problem/20/C
(10 Jan '15, 18:03)
showing 5 of 8
show all

An easier way is to use Dynamic Programming based FloydWarshall algorithm for 'all pairs shortest distances'. answered 04 Jan '15, 19:06
@vikramnitin9 Can you please give me the code using Floyd Warshall? I tried doing it using the Wikipedia pseudo code but it still didn't work :(
(05 Jan '15, 21:06)
http://pastebin.com/tQ02C6Mz Note: I have used the wikipedia pseudocode. I believe the one on iarcs site is different, I prefer this implementation.
(11 Jan '15, 10:59)

I worked out a FloydWarshall solution to this prob. and am getting a WA in 4/20 testcases. So, my score is 30/100. Please Help...
answered 09 Jan '15, 23:37
Hello @arpanb8 I have edited your code and got it accepted. Please refer the link below. I have also highlighted the lines where I have edited so that you can compare your previous code with this code and check where you went wrong. https://www.dropbox.com/s/qv6ghhnyv6zwiea/arpan%27s%20freeticket%20code.cpp?dl=0 In short, your errors were: You didn't make your infinity in your initialization of the 3D array large enough and there was a slight flaw in your implementation of the algorithm. That's pretty much it.
(12 Jan '15, 17:11)
Any time! I too got a better hold of the algorithm, debugging your code ;)
(12 Jan '15, 21:55)
I am in class 10. And if I wasn't taking INOI, I wouldn't be able to post in this forum :P
(12 Jan '15, 22:14)
