Floyd算法求最短路，怎么用？

50.Acwing基础课第854题-简单-Floyd求最短路 题目描述 给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。 再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。 数据保证图中不存在负权回路。 输入格式 \(第一行包含三个整数 n,m,k\)。 \(接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z\)。 \(接下来 k 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离\)。 输出格式 \(输出一个整数，表示从 1号点到 n 号点的最多经过 k条边的最短距离\)。 \(如果不存在满足条件的路径，则输出 impossible\)。 数据范围 \(1≤n≤200\)， \(1≤k≤n^2\)， \(1≤m≤20000\) \(图中涉及边长绝对值均不超过 10000\)。 输入样例： 3 3 2 1 2 1 2 3 2 1 3 1 2 1 1 3 输出样例： impossible 1 代码： // 包含字符串操作相关函数（本代码主要用memset，但Floyd模板常保留） #include <cstring> // 输入输出流头文件，用于cin/cout #include <iostream> // 包含min/max等算法函数，Floyd核心用到min #include <algorithm> // 命名空间声明，避免每次写std::cin/std::cout using namespace std; // 常量定义：N表示最大节点数（210适配多数Floyd题目范围），INF表示无穷大（0x3f3f3f3f约1e9，避免溢出） const int N = 210, INF = 0x3f3f3f3f; // 全局变量：n-节点数，m-边数，Q-查询次数；d[N][N]是邻接矩阵，d[i][j]表示i到j的最短距离 int n, m, Q; int d[N][N]; // Floyd-Warshall算法核心函数：求解任意两点间的最短路径 void floyd() { // k是「中转点」：枚举所有可能的中转节点 for (int k = 1; k <= n; k ++ ) // i是「起点」：枚举所有起点 for (int i = 1; i <= n; i ++ ) // j是「终点」：枚举所有终点 for (int j = 1; j <= n; j ++ ) // 核心松弛操作：比较「i直接到j」和「i经过k到j」的距离，取更小值 d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } int main() { // 输入：节点数n、边数m、查询次数Q cin >> n >> m >> Q; // 初始化邻接矩阵： // 1. 自己到自己的距离为0（i==j） // 2. 其他节点初始化为无穷大（表示初始时无直接路径） for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) if (i == j) d[i][j] = 0; else d[i][j] = INF; // 读入m条边的信息 while (m -- ) { int a, b, c; // a-起点，b-终点，c-边权 cin >> a >> b >> c; // 处理「重边」：如果a到b有多个边，只保留权值最小的那条 d[a][b] = min(d[a][b], c); } // 调用Floyd算法，更新所有节点对的最短路径 floyd(); // 处理Q次查询 while (Q -- ) { int a, b; // 查询a到b的最短路径 cin >> a >> b; int t = d[a][b]; // 判断是否可达：INF/2是安全判据（避免负权边导致dist略小于INF） if (t > INF / 2) puts("impossible"); // 不可达输出impossible else cout << t << endl; // 可达输出最短距离 } return 0; }