494. Floyd求最短路
时间限制：1000 MS 内存限制：64 MB
题目描述
# Floyd求最短路 ## 题目描述 给定一个包含 $n$ 个点、$m$ 条边的有向图，点的编号为 $1$ 到 $n$。图中可能存在重边和自环，边权可能为负数，但保证不存在负权回路。 给定 $k$ 个询问，每个询问包含两个整数 $x$ 和 $y$，要求求出从点 $x$ 到点 $y$ 的最短距离。如果不存在从点 $x$ 到点 $y$ 的路径，则输出 `impossible`。 从一个点到其自身可以不经过任何边，此时路径长度为 $0$。 ## 输入格式 从文件 `floyd.in` 中读入数据。 第一行包含三个整数 $n,m,k$，分别表示点数、边数和询问数。 接下来 $m$ 行，每行包含三个整数 $x,y,z$，表示存在一条从点 $x$ 到点 $y$、权值为 $z$ 的有向边。 接下来 $k$ 行，每行包含两个整数 $x,y$，表示询问从点 $x$ 到点 $y$ 的最短距离。 ## 输出格式 将结果输出到文件 `floyd.out` 中。 共输出 $k$ 行，按输入顺序回答每个询问： - 如果存在从点 $x$ 到点 $y$ 的路径，输出一个整数，表示最短距离。 - 否则，输出 `impossible`。 ## 数据范围 - $1 \le n \le 200$。 - $1 \le m \le 20000$。 - $1 \le k \le n^2$。 - 所有边和询问中的点编号均满足 $1 \le x,y \le n$。 - 边权 $z$ 为整数，且 $|z| \le 10000$。 - 图中允许重边、自环和负权边。 - 保证图中不存在负权回路。 ## 样例输入 ``` 3 3 2 1 2 1 2 3 2 1 3 1 2 1 1 3 ``` ## 样例输出 ``` impossible 1 ``` ## 时间与空间限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。