//floyd求最短路 #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=210,INF=1e9; int d[N][N],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++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } int main(void) { cin>>n>>m>>q; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j)d[i][j]=0; //因为存在自环,因此初始化为0,保证自环全为0 else d[i][j]=INF; while(m--) { int a,b,x; cin>>a>>b>>x; d[a][b]=min(d[a][b],x); //存在重边,保留最小边 } floyd(); while(q--) { int a,b; cin>>a>>b; if(d[a][b]>INF/2)puts("impossible"); else cout<<d[a][b]<<endl; } return 0; }
0.0分
1 人评分