A3192. 最短距离查询【Floyd】
编程题
入门
知识点
题目描述
很久很久以前，有那么一个传说，据说佛洛依德算法只要4行代码。于是乎，张老师就带着他的一群小黑子开始了学习~
给定一个 n 个顶点 m 个边的有向图，图中不存在重边和自环，边的权重都是整数。 再给定 k 次查询，每次查询包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短路径的距离。 如果路径不存在，则输出 impossible，如果存在，则输出最短路径的距离。
给定一个 n 个顶点 m 个边的有向图，图中不存在重边和自环，边的权重都是整数。 再给定 k 次查询，每次查询包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短路径的距离。 如果路径不存在，则输出 impossible，如果存在，则输出最短路径的距离。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行每行包含三个整数 x, y, z，表示存在一条从点 x 到点 y 的有向边，边的权重为 z。
接下来 k 行，每行对应依次询问，包含两个整数 a, b，表示询问从顶点 a 到顶点 b 的最短路径距离。
接下来 m 行每行包含三个整数 x, y, z，表示存在一条从点 x 到点 y 的有向边，边的权重为 z。
接下来 k 行，每行对应依次询问，包含两个整数 a, b，表示询问从顶点 a 到顶点 b 的最短路径距离。
输出格式
共 k 行，每行输出一个整数，表示这次询问的结果，如果两点间存在最短路径，则输出最短路径的距离，如果不存在，则输出 impossible。
输入输出样例
输入 #1
6 3 8 3 5 8 3 4 24 4 3 22 6 2 5 3 4 2 1 6 5 3 5 2 3 5 2 4
输出 #1
impossible impossible impossible impossible impossible impossible 8 impossible
说明/提示
$1\le n\le 200$
$1\le k\le n^2$
$1\le m\le 20000$
图中的每条边的权重值不大于 50
张帅帅
$1\le k\le n^2$
$1\le m\le 20000$
图中的每条边的权重值不大于 50
张帅帅