注意floyd在while(k–)外，一遍floyd就能把所有的节点间最短距离求出来

#include<iostream>
#include<cstring>
using namespace std;

const int N=350,INF=1e9;
int dis[N][N];
bool st[N];

int n,m,k;

void floyd(){
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
}
int main(){
    cin>>n>>m>>k;
    memset(dis,0x3f,sizeof dis);
    for(int i=0;i<n;i++)
        dis[i][i]=0;

    while(m--){
        int x,y,z;
        cin>>x>>y>>z;
        dis[x-1][y-1]=min(dis[x-1][y-1],z);
    }
    floyd();
    while(k--){
        int x,y;
        cin>>x>>y;
        if(dis[x-1][y-1]>INF/2) cout<<"impossible"<<endl;
        else cout<<dis[x-1][y-1]<<endl;
    }
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla