题解

题解如下

#include<iostream>
using namespace std;
int n,m,k;
int dis[210][210];
int s,f,w;
int a,b;
int main(){
	cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=n;j++){
        	dis[i][j]=1e9;
        }
        dis[i][i]=0;
    }
    for(int i=1;i<=m;i++){
    	cin>>s>>f>>w;
        dis[s][f]=w;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
         	for(int j=1;j<=n;j++){
               	dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
            }
        }
    }
    while(k--){
    	cin>>a>>b;
        if(dis[a][b]==1e9) cout<<"impossible"<<endl;
        else cout<<dis[a][b]<<endl;
    }
	return 0;
}