A3192 | $最短距离查询【Floyd】$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

很久很久以前，有那么一个传说，据说佛洛依德算法只要4行代码。于是乎，张老师就带着他的一群小黑子开始了学习~ 给定一个 n 个顶点 m 个边的有向图，图中不存在重边和自环，边的权重都是整数。 再给定 k 次查询，每次查询包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短路径的距离。 如果路径不存在，则输出 impossible，如果存在，则输出最短路径的距离。

第一行包含三个整数 n,m,k。 接下来 m 行每行包含三个整数 x, y, z，表示存在一条从点 x 到点 y 的有向边，边的权重为 z。 接下来 k 行，每行对应依次询问，包含两个整数 a, b，表示询问从顶点 a 到顶点 b 的最短路径距离。

共 k 行，每行输出一个整数，表示这次询问的结果，如果两点间存在最短路径，则输出最短路径的距离，如果不存在，则输出 impossible。

输入 #1

输出 #1

impossible
impossible
impossible
impossible
impossible
impossible
8
impossible

C++ 编辑器

输入

输出