题目描述

求最短路

blablabla

算法 Floyd O($n^3$)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define fs(i,x,y,z) for(int i=x;i<=y;i+=z)
const int z=1001,inf=1e9;
#define no "impossible"
int n,m,q,a[z][z];
int main(){
    cin>>n>>m>>q;
    fs(i,1,n,1){
        fs(j,1,n,1){
            if(i!=j) a[i][j]=inf;
        }
    }
    fs(i,1,m,1){
        int u,v,w;cin>>u>>v>>w;
        a[u][v]=min(a[u][v],w);
    }
    fs(i,1,n,1){
        fs(j,1,n,1){
            fs(k,1,n,1){
                a[j][k]=min(a[j][k],a[j][i]+a[i][k]);
            }
        }
    }
    fs(i,1,q,1){
        int u,v;cin>>u>>v;
        if(a[u][v]>inf/2) cout<<no;
        else cout<<a[u][v];
        cout<<endl;
    }
    return 0;
}