时间复杂度 : O(n^3)

算法思想：

1. 用一个dist表记录各个点之间的权值情况
2. 假设有1-3三个点，需要遍历这3个点分别作为中转点时，对其他点到点的路径权值有无优化。打个比方，2 -> 3(权值为5),2 -> 1(权值为1),1 -> 3(权值为2),第一轮遍历时，以1为中转点,优化思路时，dist[2][3] = min(dist[2][3],dist[2][1]+dist[1][3]);可以发现，如果2先经过1再到3会有优化。
3. 以1为中转时，遍历一边表格内的所有格子需要两层循环，但是我们还要尝试以1-n为中转时的优化。所以总共需要三层循环。

笔试技巧：

1. 迭代格子时，主对角线上的格子不用迭代，因为它代表自己到自己的路径。
2. 以i作为中转点作为路径权值优化迭代时，第i行和第i列可以直接不用计算，因为它们分别代表自己到别人，别人到自己的情况，若以自己为中转点，路径肯定没有变化，因此直接忽略。

代码：
需要注意的点: 它不像prim,kruskal,dijkstra，需要用g[N][N]邻接矩阵来记录各点之间的权值，它直接用dist记录就好，方便后续直接在dist上迭代

#include <bits/stdc++.h>
using namespace std;

int n,m,Q;
const int INF = 0x3f3f3f3f;
const int N = 333;
int dist[N][N];

int main(){

    cin >> n >> m >> Q;
    memset(dist,INF,sizeof dist);

    //不要忘了自己到自己是0
    for(int i = 1; i <= n; i++ ) dist[i][i] = 0;

    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b],c);
    }

    //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]);
            }
        }
    }

    while(Q--){
        int d,e;
        cin >> d >> e;
        if(dist[d][e] > INF/2) cout << "impossible" << endl;
        else cout << dist[d][e] << endl;
    }


    return 0;
}