floyd:思想是动态规划，遍历更新了每个点
可能存在负权边，所以当 dist[i][j] = INF, dist[i][k] = INF, dist[k][j] = -10时，那么dist[i][j]就会被更新成INF - 10，但此时i和j仍然是不连通的。

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const  int N = 210, INF = 0x3f3f3f3f;
int m, n, dist[N][N], k;

//floyd 就是三重循环，思想是动态规划
void floyd()
{
    for(int k = 1; k <= n; k ++)
        for(int i = 1;  i <= n; i++)
            for(int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j]);
}


int main()
{
    cin.tie(0);
    cin >> n >> m >> k;

    memset(dist, 0x3f, sizeof dist);

    //处理自环
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i == j)  dist[i][j] = 0;

    while(m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        dist[x][y] = min(dist[x][y], z);
    }

    floyd();

    while(k--)
    {
        int a, b;
        cin >> a >> b;
        if(dist[a][b] > INF / 2) puts("impossible");
        else    cout << dist[a][b] <<endl;
    }
}