1699: Floyd求最短路
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：52
Solved：15
Description
给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。
Input
第一行包含三个整数n，m，k
接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
接下来k行，每行包含两个整数x，y，表示询问点x到点y的最短距离。
接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
接下来k行，每行包含两个整数x，y，表示询问点x到点y的最短距离。
Output
输出共k行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出“impossible”。
Sample Input Copy
4 8 3
1 0 2
0 3 -4
2 0 7
2 0 6
1 2 5
2 3 -3
3 2 12
3 0 7
0 1
1 3
2 0Sample Output Copy
impossible
-2
4
HINT
1≤n≤200, 1≤m≤20000 , 1≤k≤n^2 。
图中涉及边长绝对值均不超过10000。
图中涉及边长绝对值均不超过10000。