【题目来源】
AcWing：854. Floyd求最短路 - AcWing题库
【题目描述】
给定一个\(n\)个点\(m\)条边的有向图，图中可能存在重边和自环，边权可能为负数。再给定\(k\) 个询问，每个询问包含两个整数\(x\)和\(y\)，表示查询从点\(x\)到点\(y\)的最短距离，如果路径不存在，则输出 impossible。数据保证图中不存在负权回路。
【输入】
第一行包含三个整数 \(n, m,k\)。接下来\(m\)行，每行包含三个整数\(x,y,z\)，表示存在一条从点\(x\) 到点\(y\)的有向边，边长为\(z\)。
接下来\(k\)行，每行包含两个整数\(x,y\)，表示询问点\(x\)到点\(y\)的最短距离。
【输出】
共\(k\) 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出impossible。
【输入样例】
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
【输出样例】
impossible
1
【算法标签】
《AcWing 854 Floyd求最短路》 #最短路# #Floyd#
【代码详解】
#include <bits/stdc++.h> // 包含所有标准库头文件
using namespace std;const int N = 210, INF = 1e9; // 定义常量N为210，INF为一个很大的数（表示无穷大）
int dist[N][N]; // 定义一个二维数组dist，用于存储任意两点之间的最短距离
int n, m, q; // n表示图中节点的数量，m表示边的数量，q表示查询的数量// Floyd-Warshall算法实现
void floyd()
{// 三重循环，k是中间节点，i是起点，j是终点for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)// 更新i到j的最短距离，考虑通过k节点的情况dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}int main()
{// 输入节点数n，边数m，查询数qcin >> n >> m >> q;// 初始化dist数组for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)if (i == j) dist[i][j] = 0; // 节点到自身的距离为0else dist[i][j] = INF; // 其他节点之间的距离初始化为无穷大// 输入m条边，并更新dist数组while (m--) {int a, b, c;cin >> a >> b >> c; // 输入边的起点a，终点b，权重cdist[a][b] = min(dist[a][b], c); // 更新a到b的最短距离，保留最小的权重}// 调用Floyd-Warshall算法计算所有节点对之间的最短路径floyd();// 处理q个查询while (q--) {int a, b;cin >> a >> b; // 输入查询的起点a和终点bint ans = dist[a][b]; // 获取a到b的最短距离// 如果最短距离大于等于INF/2，说明a和b之间没有路径（或路径不可达）if (ans >= INF / 2) cout << "impossible" << endl; // 输出"impossible"else cout << ans << endl; // 否则输出最短距离}return 0; // 程序结束
}
【运行结果】
3 3 2
1 2 1
2 3 2
1 3 1
2 1
imposssible
1 3
1