下列代码试图实现Floyd算法求所有点对之间的最短路径，横线处应填入（ ）。 void floyd(int n, int dist[][MAXN]) { for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (___________) // 在此处填入选项 dist[i][j] = dist[i][k] + dist[k][j]; }
A：dist[i][k] + dist[k][j] < dist[i][j]
B：dist[i][k] != INF && dist[k][j] != INF
C：dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]
D：dist[i][j] == INF
正确答案：C
答案解析
Floyd算法通过动态规划更新任意两点间的最短路径。外层循环遍历中间点k，内层双循环遍历起点i和终点j。核心操作是比较经过中间点k的路径是否比当前记录的路径更短。更新条件依赖于从i到k和从k到j的路径存在且其距离之和小于当前i到j的距离。因此需判断dist[i][k]与dist[k][j]均不为无穷大，并计算二者之和作为候选值参与比较。算法本质是在三重循环中持续优化路径估计值。
试卷来源：202603 CCF-GESP编程能力等级认证C++八级真题