Help solving Floyd Warshall algorithm

№	Пользователь	Рейтинг
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

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
4	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
8	Dominater069	154
8	nor	154

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;
}