I have used floyd warshall algorithm but I am getting WA. Have tried most of the spoj toolkit and my created cases.
Code removed . Ac now, thanks again to @simes for pointing out my stupidity.
Jul '19
Jul '19
When you tried the SPOJ Toolkit cases, did you get the right answer?
76 19
16 15 19
26 69 9
17 30 46
23 28 18
17 55 62
69 76 46
31 21 13
23 75 66
10 16 54
32 19 11
30 57 89
66 1 61
36 57 46
55 10 33
15 28 75
73 74 18
21 26 9
66 36 74
75 31 33
If the toolkit is to be believed, the expected answer is 0.000003 percent, but your code gives 0.004600 percent.
I actually have a doubt regarding this problem. Earlier I was using prim’s mst to solve this but I realised it was only greedy so there were chances that it would miss some cases like one i have originally posted with the problem. But can i use floyd warshall here and not miss any cases like this . It’s dp so I think it shouldn’t miss any. In comments I saw people have solved this with greedy based modified dijsktra. Am I missing something in the problem ?
It’s not hard to think of a scenario where the minimum spanning tree won’t give the minimum distance between the source and destination vertices. Dijkstra or Floyd Warshall is what you need.
I used Dijkstra, since it’s single source and destination, but FW will also work if you fix the code within the nested loops.
I was of the opinion that dijsktra and mst were similar in approach and greedy. Can you suggest as to how to implement dijkstra in dp way ? Floyd warshall according to me is the dp method of dijsktra, which I have already used here. If you can suggest any changes in the nested loops that I might be doing wrong.
Yes, but both being greedy and similar doesn’t mean they answer the same question.
I changed the order of the i,j,k when accessing ar, and it then gave the expected answer for the test I gave previously.
Sometimes I think I am an idiot. I should be running the loop for all vertices one by one but I am only resetting it for each column. Thanks @simes . AC now.
Also understood " but both being greedy and similar doesn’t mean they answer the same question." I should really stop coding during office time.
