题目来源： https://www.acwing.com/problem/content/856/
给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。
数据保证图中不存在负权回路。
输入格式
第一行包含三个整数n，m，k
接下来m行，每行包含三个整数x，y，z，表示点x和点y之间存在一条有向边，边长为z。
接下来k行，每行包含两个整数x，y，表示询问点x到点y的最短距离。
输出格式
共k行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出“impossible”。
数据范围
1≤n≤200,
1≤k≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过10000。
输入样例：
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例：
impossible
1
顶点比较少的稠密图，显然用floyed算法更合适，同时这个是带有负权的floyed算法。直接套用书中floyed算法，会有一些问题，对于带负权图，应该在松弛前判定是否连通，如果不连通，是不能松驰的，否则因为带负权，两条本不连通的会变成连通。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0X3F3F3F;
int g[201][201];
int n, m, k;
void floyed(){
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(g[i][k]<INF && g[k][j]<INF) // 要连通
g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
}
int main(){
cin >> n >> m >> k;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++)
g[i][j] = (i==j ? 0 : INF);
}
for(int i=1; i<=m; i++){
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
g[x][y] = min(g[x][y], z);
}
for(int i=1; i<=n; i++)
g[i][i] = 0;
floyed();
for(int i=1; i<=k; i++){
int x, y;
scanf("%d %d", &x, &y);
if(g[x][y]==INF)
printf("impossible\n");
else
printf("%d\n", g[x][y]);
}
return 0;
}