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