基础其实就是暴力

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1005][1005],q;
void floyd(){
    for(int k=1;k<=n;k++){//k为ij间的媒介
        for(int i=1;i<=n;i++){//遍历i
            for(int j=1;j<=n;j++){//遍历j
                a[i][j]=min(a[i][j],a[i][k]+a[k][j]);//i ->(a[i][k]) k ->(a[k][j]) j
            }
        }
    }
}
int main(){
	cin>>n>>m>>q;
    memset(a,0x3f,sizeof a);//注意要定义为大数，否则min会算入0
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        a[x][y]=z;//有向图输入
    }
    floyd();
    while(q--){
        int s,e;
        cin>>s>>e;
        if(a[s][e]!=0x3f3f3f3f){//注意int有4字节，存储时会有4倍，所以要改判断
            cout<<a[s][e];
        }
        else{
            cout<<"impossible";
        }
        cout<<endl;//判断+输出
    }
    return 0;
}