A29680.最短距离查询【Floyd】

很久很久以前，有那么一个传说，据说佛洛依德算法只要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\le n\le 200$
$1\le k\le n^2$
$1\le m\le 20000$

图中的每条边的权重值不大于 50


张帅帅