我们令 f[i][j] 表示从 i-->j的最短路上j前面的那个点.
显然初始化时 f[i][j]=i; (这样的话先判断一下i是否能到达j好点)
更新条件时，当发现通过点k能使最短路径减少，则 f[i][j]=f[k][j]这也是显然的，相当于把k-->j这条路接在了i--->k上，i-->j的倒数第二个点理应是k-->j时候的那个点。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int e[105][105],pre[105][105];
int n,m;
void init()
{
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
e[i][j]=(i==j?0:inf);
pre[i][j]=i;
}
}
void floyd()
{
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(e[i][j]>e[i][k]+e[k][j]) {e[i][j]=e[i][k]+e[k][j]; pre[i][j]=k;}
}
void output(int s,int e)
{
if(s==e) {cout<<s<<" ";return;}
int k=pre[s][e];
output(s,k);
cout<<e<<" ";
}
int main()
{
int i,j,a,b,c,q;
cin>>n>>m;
init();
for(i=1;i<=m;++i) cin>>a>>b>>c,e[a][b]=c; //单向边
floyd();
cin>>q;
while(q--){
cin>>a>>b;
cout<<e[a][b]<<" :";
output(a,b);
cout<<endl;
}
return 0;
}