1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int maxn=110; 6 int f[maxn][maxn]; 7 int ff[maxn][maxn]; 8 bool hav[maxn][maxn]; 9 int n,m,a,b,c; 10 int main(){ 11 memset(f,0x3f3f3f3f,sizeof(f)); 12 memset(hav,false,sizeof(hav)); 13 scanf("%d%d",&n,&m); 14 for(int i=1;i<=m;++i){ 15 scanf("%d%d%d",&a,&b,&c); 16 f[a][b]=0; 17 f[b][a]=0; 18 ff[a][b]=c; 19 ff[b][a]=c; 20 hav[a][b]=true; 21 hav[b][a]=true; 22 } 23 scanf("%d",&m); 24 for(int i=1;i<=m;++i){ 25 scanf("%d%d",&a,&b); 26 f[a][b]=ff[a][b]; 27 f[b][a]=f[a][b]; 28 } 29 for(int k=1;k<=n;++k){ 30 for(int i=1;i<=n;++i){ 31 for(int j=1;j<=n;++j){ 32 if(hav[i][k] && hav[k][j]){ 33 f[i][j]=min(f[i][j],f[i][k]+f[k][j]); 34 hav[i][j]=true; 35 } 36 } 37 } 38 } 39 scanf("%d%d",&a,&b); 40 printf("%d",f[a][b]); 41 return 0; 42 }