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.
CHICAGO
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.
Oh I hadn’t spotted that! It looks like I was chasing a red herring then.
A smiley can really help in these times. Don’t know whether I was scolded or just a happy remark.
If I was scolding anybody, it was myself for missing the real problem.
Here you go…
