What I thought of is there must be some state j to which we first go and then buy the fuel for the rest of the journey from the state j.
My dp[i][j] denotes the minimum cost of fuel needed to go from state i to state j.
So, my dp transition is dp[i][k] = dp[i][j] + fuel[j] * dist[j][k], where dist[i][j] is the minimum distance from state i to state j.
But, when I submitted this, it fails on some of the test cases.
So, then I tried dp[i][k] = dp[i][j] + dp[j][k] and it passed!
I didn’t understand whether I am going wrong OR the test cases are weak.
Can someone please help?
Interesting. I will get back to it in a while. Meanwhile if you want the pdf of (unapproved) editorial, I can provide you that if it helps. Tester and Setter’s solution use “dp[i][k] = dp[i][j] + fuel[j] * dist[j][k],” thing itself, so I think their approach and solutions are correct.
See hardworking editorialist.
Writing editorial for last question + replying on discuss + replying on FB + replying on mail + mailing editorials to people + …
I was thinking almost the same idea and failed in some submissions then i read this post, i got accepted and i understood why changing the transition you mentioned above works.
Lets calculate W[ i ][ j ] := the minimum cost needed to go from node i to node j if you can only buy fuel at node i, then the answer is W[ i ][ j ] = fuel[ i ]*dist[ i ][ j ].
And you can imagine this as a completed graph wich each edge is weighted with W[ i ][ j ] and if you calculate the minimum path between nodes P and Q you will get the answer for the problem.
And this is the reason of the change in the transition.
Hope this approach helps you, because i was making the same idea.
The answer to the problem can be modeled as a subsequence of nodes P = x_1 , x_2 , ... , x_k = Q such that you bought the minimun fuel needed in node x_i to reach node x_{i+1}. Note that x_i is not neccesary adjacent to x_{i+1}.
For example, in the test case of the problem the subsequence will be 1 , 3 , 4 which means that you bought the minimun fuel needed in node 1 to reach node 3 and then you bought the minimun fuel needed to reach node 4.
Why can we do this? Because if we don’t buy the minimun fuel needed in x_i to reach x_{i+1} we have two cases:
If fuel[ x_i ] < fuel[ x_{i+1} ] then we should have bought more fuel in node x_i instead of buy in node x_{i+1} to continue our path.
If fuel[ x_i ] > fuel[ x_{i+1} ] then we should have bought the minimun fuel needed to reach x_{i+1}.
So with this, we can calculate W[i][j] as i said before. Note that this is a complete directed graph, because W[i][j] is not necessary equal to W[j][i].
And with this in mind and the first part, the solution to the problem is the minimum distance between P and Q in this new graph described by W[i][j], because this will represent the sequence.
Sorry brother…just one more thing I want to clear…
I am not saying that we brought all the fuel at p itself while going from p to q. Rather, I would go to some node j (which have the less cost of fuel probably) and we continue our journey from j to q by buying all required fuel at state j itself.
Now, this process is recursive as while going from p to j, I don’t take the entire fuel at state p, rather I used the same argument for going from the state p to state j.
Yes, it is not necessary buy all the fuel in node P. What i’m saying is that we need to buy the minimum amount of fuel needed to reach some node j from P and then try to go to Q in the cheapest way, and here is where we need the DP. But this problem becomes in the shortest path in graph W describe above.
And the nodes in the shortest path (in this graph W, not the original) represent the sequence.
+ …
.