Floyd算法 时间复杂度$O(V^3)$

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

const int N=205;
const int INF=0x3f3f3f3f;
int n,m,Q;
int D[N][N];

void Floyd(){
    for(int k=1; k<=n; ++k){
        for(int i=1; i<=n; ++i){
            for(int j=1; j<=n; ++j){
                D[i][j]=min(D[i][j], D[i][k]+D[k][j]);
            }
        }
    }
}



int main(){
    // Floyd算法
    cin>>n>>m>>Q;
    memset(D, 0x3f, sizeof D);
    for(int i=1; i<=n; ++i) D[i][i]=0; // 自环设置为0

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

    Floyd();

    while(Q--){
        cin>>x>>y;
        if(D[x][y]>INF/2) cout<<"impossible"<<endl;
        else cout<<D[x][y]<<endl;
    }

    return 0;
}