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、查询次数Qcin >> 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"); // 不可达输出impossibleelse cout << t << endl; // 可达输出最短距离}return 0;
}