Help solving Floyd Warshall algorithm

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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!

Code

int n, r, q;
const int mxn = 85;
int dp[mxn][mxn][mxn];
int cost[mxn];
int maxCost[mxn][mxn][mxn];
int test = 1;
void solve() {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= n; k++) {
                dp[i][j][k] = IINF;
                maxCost[i][j][k] = -1;
            }
        }
    }
    for (int i = 1; i <= n; i++) cin >> cost[i];
    for (int i = 1; i <= n; i++) {
        dp[i][i][0] = 0;
        maxCost[i][i][0] = cost[i];
    }
    for (int i = 0; i < r; i++) {
        int u, v, w; cin >> u >> v >> w;
        int newMaxCost = max(maxCost[u][u][0], maxCost[v][v][0]);
        if (dp[u][v][0] + maxCost[u][v][0] > w + newMaxCost) {
            dp[u][v][0] = dp[v][u][0] = w;
            maxCost[u][v][0] = maxCost[v][u][0] = newMaxCost;
        }
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dp[i][j][k - 1] != IINF) {
                    if (dp[i][j][k] + maxCost[i][j][k] > dp[i][j][k - 1] + maxCost[i][j][k - 1]) {
                        dp[i][j][k] = dp[i][j][k - 1];
                        maxCost[i][j][k] = maxCost[i][j][k - 1];
                    }
                }
                if (dp[i][k][k - 1] != IINF && dp[k][j][k - 1] != IINF) {
                    int newMaxCost = max(maxCost[i][k][k - 1], maxCost[k][j][k - 1]);
                    if (dp[i][j][k] + maxCost[i][j][k] > dp[i][k][k - 1] + dp[k][j][k - 1] + newMaxCost) {
                        dp[i][j][k] = dp[i][k][k - 1] + dp[k][j][k - 1];
                        maxCost[i][j][k] = newMaxCost;
                    }
                }
            }
        }
    }
    
    cout << "Case #" << test++ << nline;
    for (int m = 0; m < q; m++) {
        int u, v; cin >> u >> v;
        if (dp[u][v][n] != IINF) cout << dp[u][v][n] + maxCost[u][v][n] << nline;
        else cout << -1 << nline;
    }
    cout << nline;
}

Comments (9)

Write comment?

-is-this-fft-

12 days ago, # |

+33

Consider this test case:

5 5 1
100 1000 1 1 10000
4 1 10
1 3 10
4 2 1
2 3 1
3 5 1
4 5

Your code prints 10021, but I think the correct answer is 10003. If I understand your logic correctly, here is your problem: you calculate dp[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.

Here's how I would solve this problem

→ Reply

lvisbl_

12 days ago, # ^ |

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:

write a very naive solution (try all paths or something) or copy someone else's if you can
write a program to generate thousands of small test cases
use those two to find a test case where your solution gives the wrong answer.

11 days ago, # ^ |

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.

5 days ago, # ^ |

← Rev. 2 →

Hi sir, I have this question hang around my mind recently, during doing the shortest path algorithms such as Floyd, Bellman,.. If I do proper DP without space optimization, I see that I have DAG and the relaxation will follow the topological sort from smaller states to bigger states. But if I do space optimization, we will not have DAG anymore in terms of relaxation order. But I also know that even if the relaxation order is not correct and not follow the DAG, the answer is still correct because the relaxations that not follow the correct topo order will not make the answer more worse but always equal or better. Somehow, I can not proof the correctness of it. And I do not know the keyword to "describe" this phenomenal, can you help me to point the term out. Thank in advance!

123gjweq2

Red coders will always say it is just practice but, in reality, it is $$$IQ$$$ and practice is just a way to express the $$$IQ$$$. Imagine $$$IQ$$$ is like how tall you are and codeforces is like basketball. No amount of practice can make a $$$5'0$$$ guy have the same skill as a $$$8'0$$$ guy.

I think your mindset is the problem

But let me ask you this: if it were $$$100$$$% practice, then why'd he add this in?

It seems to me like he just thought of it and had no idea how the thought came about. My thought is: if it were experience, surely he'd see that his thought came from something he did in his past experience (and so he would have said "experience" more confidently in his comment). But maybe I am wrong.

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..

code

#include <bits/stdc++.h>
#define MAX 85
using namespace std;
const int INF = 1e9 + 7;

int C, R;
int dist[MAX][MAX];
int maxCost[MAX][MAX];
int f[MAX];

void FloydWarshall() {
    int times = 2;

    while (times--) {
        for (int k = 1; k <= C; k++) {
            for (int i = 1; i <= C; i++) {
                for (int j = 1; j <= C; j++) {
                    int maxFeast = max(maxCost[i][k], maxCost[k][j]);
                    if (dist[i][j] + maxCost[i][j] > dist[i][k] + dist[k][j] + maxFeast) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        maxCost[i][j] = maxFeast;
                    }
                }
            }
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);
#endif
    int u, v, w, Q, t = 1;

    while (cin >> C >> R >> Q) {
        if (C == 0) {
            break;
        }

        for (int i = 1; i <= C; i++) {
            cin >> f[i];
        }

        for (int i = 1; i <= C; i++) {
            for (int j = 1; j <= C; j++) {
                dist[i][j] = INF;
                maxCost[i][j] = max(f[i], f[j]);
            }
        }

        for (int i = 0; i < R; i++) {
            cin >> u >> v >> w;
            dist[u][v] = dist[v][u] = w;
        }

        FloydWarshall();
        
        if (t > 1) {
            cout << endl;
        }
        cout << "Case #" << t++ << endl;

        for (int i = 0; i < Q; i++) {
            cin >> u >> v;
            cout << (dist[u][v] == INF ? -1 : dist[u][v] + maxCost[u][v]) << endl;
        }
    }
    return 0;
}

lvisbl_'s blog