题解

G[s,i,j]表示只允许经过1-s点，从i到j的最短距离
G[s,i,j]=min(G[s-1,i,k]+G[s-1,k,j])

代码

#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
const int N=210;
int G[N][N],n,m,k;
void floyd(){
    for(int s=1;s<=n;s++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                G[i][j]=min(G[i][j],G[i][s]+G[s][j]);
            }
        }
    }
}
int main(void){
    memset(G,0x3f,sizeof G);
    cin>>n>>m>>k;
    int a,b,c;
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        G[a][b]=min(G[a][b],c);//可能有重边，保证最小的
    }
    for(int i=1;i<=n;i++) G[i][i]=0;//可能有自环，等输入完了都弄成0
    floyd();
    for(int i=0;i<k;i++){
        cin>>a>>b;
        if(G[a][b]>0x3f3f3f3f/2) cout<<"impossible"<<endl;
        else cout<<G[a][b]<<endl;
    }
}