1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<string> 7 #define cl(a,b) memset(a,b,sizeof(a)) 8 #define debug(x) cerr<<#x<<"=="<<(x)<<endl 9 using namespace std;10 typedef long long ll;11 12 const int maxn=110;13 14 int f[maxn],tol,n,m;15 16 struct _edge17 {18     int u,v,w;19 }edge[maxn*maxn*maxn];20 21 bool cmp(_edge a,_edge b)22 {23     return a.w<b.w;24 }25 26 void addedge(int u,int v,int w)27 {28     edge[tol].u=u;29     edge[tol].v=v;30     edge[tol].w=w;31     tol++;32 }33 34 int _find(int x)35 {36     if(f[x]==-1) return x;37     else return f[x]=_find(f[x]);38 }39 40 int kruskal()41 {42     cl(f,-1);43     sort(edge,edge+tol,cmp);44     int cnt=0,ans=0;45     int u,v,w,f1,f2;46     for(int i=0; i<tol; i++)47     {48         u=edge[i].u;49         v=edge[i].v;50         w=edge[i].w;51         f1=_find(u);52         f2=_find(v);53         if(f1!=f2)54         {55             ans+=w;56             f[f1]=f2;57             cnt++;58         }59         if(cnt==n-1) break;60     }61     return ans;62 }63 64 int main()65 {66     while(scanf("%d",&n)!=EOF&&n)67     {68         tol=0;69         for(int i=0;i<n;i++)70         {71             for(int j=0;j<n;j++)72             {73                 int x;74                 scanf("%d",&x);75                 addedge(i,j,x);76             }77         }78         scanf("%d",&m);79         for(int i=0;i<m;i++)80         {81             int x,y;82             scanf("%d%d",&x,&y);83             addedge(x-1,y-1,0);84             addedge(y-1,x-1,0);85         }86         printf("%d\n",kruskal()); 87     }88     return 0;89 }90 /*91 92 393 0 990 69294 990 0 17995 692 179 096 197 1 298 99 */