Floyd算法实战：解决洛谷P1119灾后重建最短路径问题

题目描述了一个在地震后需要重建村庄的场景。只有两个村庄都重建完成后，连接它们的公路才能通车。给定每个村庄的重建完成时间，以及一系列关于某天从村庄x到村庄y的最短路径的查询，我们需要对每个查询给出答案。

Floyd算法解析

Floyd算法是一种经典的多源最短路径算法，用于计算图中所有顶点对之间的最短路径。

它的核心思想基于动态规划。考虑从顶点 i 到 j 的最短路径，我们逐步引入中间点 k，并通过比较已知的 i->j 路径和经过 k 的路径 i->k->j 来更新最短距离。这正是动态规划思想在图论中的典型应用。

其经典的三重循环形式如下：

for(int k=0; k<n; k++)
  for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
      if(判断条件) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

解题思路

Floyd算法枚举中间点 k 的思想非常适合本题。我们注意到，只有重建完成的村庄才能作为通车的中间点。因此，对于每个询问，我们只需要将所有修复时间不超过当前询问时间 t 的村庄作为中间点，逐步更新所有点对之间的最短路即可。由于询问中的时间 t 是不下降的，我们可以按顺序递增地添加新的村庄作为中间点，避免了重复计算。

具体步骤与代码实现

1. 初始化：使用邻接矩阵存储图，将没有直接连边的点对距离初始化为无穷大（INF），自己到自己的距离为0。
2. 处理查询：顺序读取每个询问 (x, y, qt)。维护一个指针 qk，表示下一个待加入的村庄索引。循环检查并加入所有重建时间 t[qk] <= qt 的村庄 k，将其作为中间点执行Floyd的松弛操作。
3. 输出答案：如果查询时村庄 x 或 y 尚未重建完成，或者两点间距离仍为 INF（不可达），则输出 -1；否则输出计算出的最短路径长度 f[x][y]。

下面是完整的C++实现代码：

#include<bits/stdc++.h>
using namespace std;

int n, m, q, t[205];
int f[205][205];
const int INF = 0x3f3f3f3f;

int main(){
    cin >> n >> m;
    for(int i=0; i<n; i++) cin >> t[i];

    // 初始化邻接矩阵
    memset(f, 0x3f, sizeof(f));
    for(int i=0; i<n; i++) f[i][i] = 0;

    // 读入边
    int u, v, w;
    while(m--){
        cin >> u >> v >> w;
        f[u][v] = f[v][u] = w; // 无向图
    }

    cin >> q;
    int x, y, qt, qk = 0; // qk指向下一个待加入的村庄
    while(q--){
        cin >> x >> y >> qt;

        // 将重建时间不超过当前查询时间qt的所有村庄作为中间点加入并更新
        while(qk < n && t[qk] <= qt){
            int k = qk;
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    // 防止溢出，只更新有效路径
                    if(f[i][k] < INF && f[k][j] < INF){
                        f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
                    }
                }
            }
            qk++; // 处理下一个村庄
        }

        // 判断并输出结果
        if(t[x] > qt || t[y] > qt || f[x][y] == INF) cout << -1 << endl;
        else cout << f[x][y] << endl;
    }
    return 0;
}

广东的冬天，总是难以捉摸，中午热得冒汗，晚上码字时又开始觉得冷。

2026年的第一篇更新，今年跨年倒是仪式感十足。吃了一顿美味绝伦的火锅，稍微打扮了一下自己，还去看了心心念念的《寻秦记》电影，一瞬间仿佛整个青春都回来了。

电影剧情延续了电视剧的主线，但受限于时长，无法像剧集那样展开多条故事线，更像是对经典的致敬，对青春记忆的一次唤醒。我们怀念的，或许不只是故事本身，还有当年追剧的那些人和那时的自己……当《天命最高》的前奏响起时，心中涌起一阵莫名的感动。二十多年过去，总会隔一段时间就重温一遍剧集，我想很多人都懂这种感受。总是偏爱老电影、老剧，大概是怕一探索新领域就碰上烂片，既浪费时间又浪费生命吧（除非朋友强力推荐确实好看的🤩）。

最近很少追问“意义”了。世上本无新鲜事，所谓的意义往往带有目的性。一旦做事带上目的，就难免产生期待和控制欲，无法纯粹。有就有，没有也挺好。反正事情已经到这一步了，那就必须做下去。结果如何并不那么要紧，要紧的是在这个过程中，自己放下了什么。这大概也是“人教人教不会，事教人一次就会”的真实写照。

“应无所住”，是“破”的功夫，要能超脱表象；“而生其心”，是“立”的境界，回归本性能生发无限可能。

唯叹一句：道阻且长！😁

希望这篇关于Floyd算法应用的解析能对你有所帮助。如果你对图论或其他算法有更多兴趣，欢迎来云栈社区交流讨论，这里有许多热爱技术的开发者一起学习成长。