floyd模板题(含AC代码）

前言

这题纯纯 floyd 模板题。给不熟悉 floyd 的孩子们科普一下：

一、算法背景

在图论中，全源最短路径问题（All-Pairs Shortest Paths）需要找出任意两点之间的最短路径。Floyd算法（Floyd-Warshall算法）是一种经典、简单且高效的解决方案，适用于边权为正或负（但不能有负权环）的稠密图。

二、适用场景

有向图或无向图。
边权可以为负数（但不能存在负权回路）。
需要计算所有点对之间的最短距离。

三、核心思想

Floyd算法的核心是动态规划：通过枚举每一个中转点 $k$ ，检查是否能优化 $i$ 到 $j$ 的路径。其状态转移方程为：

$$dp_{i, j} = min(dp_{i, k} + dp_{j, k}, dp{i, j})$$

状态转移方程解释：
若从 $i$ 直接到 $j$ 的路径比从 $k$ 中转的路径更长，就更新路径。

四、floyd代码模板（注意不是本题AC代码）

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9; // 表示不可达
const int N = 105;   // 最大点数
int dis[N][N];       // 存储最短路径

int main() {
    int n, m; // 点数，边数
    cin >> n >> m;

    // 初始化：自己到自己是0，其他为INF
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dis[i][j] = (i == j ? 0 : INF);

    // 读入边，处理重边
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dis[u][v] = min(dis[u][v], w);
    }

    // Floyd核心三重循环
    for (int k = 1; k <= n; k++)      // 枚举中转点
        for (int i = 1; i <= n; i++)    // 枚举起点
            for (int j = 1; j <= n; j++) // 枚举终点
                if (dis[i][k] + dis[k][j] < dis[i][j])
                    dis[i][j] = dis[i][k] + dis[k][j];

    // 输出结果
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dis[i][j] == INF) cout << "INF ";
            else cout << dis[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

本题思路

首先初始化每条边为 INF（因为题目不保证每两个节点都有连边），随后再根据给的边和边权建边，随后 floyd 一下，最后输出询问答案即可。

AC代码

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
int n, m, k;
int s[1145][1145];
int sx, f, w;
int a, b;
const int INF = 1e9+7;
main() {
    cin.tie(nullptr);
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= n; j ++) {
			s[i][j] = INF;
		}
		s[i][i] = 0; // 自己到自己的边权是0
	}
	for(int i = 1; i <= m; i ++) {
		cin >> sx >> f >> w;
		s[sx][f] = w; // 建边
	}
	for(int k = 1; k <= n; k ++) {
		for(int i = 1; i <= n; i ++) {
			for(int j = 1; j <= n; j ++) {
				s[i][j] = min(s[i][k]+s[k][j], s[i][j]); // 选从i到k再从k到j 和 从i直接到j 中选一个最短的。
			}
		}
	}
	while(k --) {
		cin >> a >> b;
		if(s[a][b] == INF) cout << "impossible" << '\n';
		else cout << s[a][b] << '\n';
	}
	return 0;
}

最后祝大家都能 rp++。