Floyd求最短路径

原题链接

代码

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

const int N=210,M=20010,INF=0x3f3f3f3f;

int g[N][N];
int n,m,Q;

void floyd(){
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
int main(){
    cin>>n>>m>>Q;
    memset(g,0x3f,sizeof g);
    for(int i=1;i<=n;i++)
        g[i][i]=0;
    while(m--){
        int x,y,z;
        cin>>x>>y>>z;
        g[x][y]=min(z,g[x][y]);
    }
    floyd();

    while(Q--){
        int a,b;
        cin>>a>>b;
        if(g[a][b]>INF/2)puts("impossible");//边权可能为负数
        else cout<<g[a][b]<<endl;
    }
    
    return 0;
}