Recently, I have encountered this Floyd Warshall problem, that the problem adds extra constraint on the shortest path (all edge weights + 1 largest vertice on the path). Following my understanding, Floyd Warshall is dynamic programming and when we "relax" the state, I will add that extra condition.
So, I call dp[i][j][k]: the min distance between i and j vertices, and the middle vertices consisting only the first k vertices. And maxCost[i][j][k] is the max cost vertice of the path I have chosen in dp[i][j][k]. So my transition:
if (dp[i][j][k] + maxCost[i][j][k] > dp[i][k][k — 1] + dp[k][j][k — 1] + max(maxCost[i][k][k — 1], maxCost[k][j][k — 1]) or if the last chosen path for two vertices i and j has larger cost for the path for i, j and k is in the middle of the path, then I relax distance between i and j, and set new maxCost for that path. But there is problem with this logic can you help to point it out. Thank!
Consider this test case:
Your code prints
10021
, but I think the correct answer is10003
. If I understand your logic correctly, here is your problem: you calculatedp[4][3][3]
to be 20 (and not 2): even though $$$4 \to 2 \to 3$$$ has edges summing to only 2, the feast at 2 would cost 1000, meanwhile by going $$$4 \to 1 \to 3$$$ you pay 20 for the edges but 100 for the feast. Here's why this breaks: once you include 5, the feast will be held there and it turns out that going $$$4 \to 2 \to 3$$$ would have been cheaper after all.Use normal Floyd-Warshall (without all that
maxCost
stuff), but in the outermost loop, don't go from $$$k = 1$$$ to $$$n$$$, instead go in the increasing order of the cost of holding the feast in city $$$k$$$. When queried about cities $$$u$$$ and $$$v$$$, take the minimum over allk
ofdp[u][v][k] + max(cost[u], cost[v], cost[k])
.Thank you so much for pointing it out, I have understood why my logic failed. But during debug this kind of problem, it took me so much time and still did not know where the logic failed. So, another question.. How do you come up with the test case.
Experience I guess. After reading what you said in the blog I quickly thought "but what if you choose a more expensive path because it has a cheaper feast, and then it turns out you won't use that feast anyway". Then I just constructed a test case to prove that this can happen.
What you also can do is:
Thank you so much, I have got AC following you suggestion and it's satisfied me enough.
Btw just for curiosity, below, I have sent another code which run the same failed logic two times and it is working (got AC too). It's like some kind of convergence because of two parameters depend each other (min dist and max cost), but I have no idea how it's work.
Hi, I have this arbitrary code from my peer and with the same idea, he said that if I run Floyd 2 times, the logic will work. Can you help to explain this..