Constructing Roads

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int n,m,k,a,b,ans;
 5 int now[110],map[110][110];
 6 bool v[110];
 7 int main(){
 8     scanf("%d",&n);
 9     for(int i=1;i<=n;i++)
10     for(int j=1;j<=n;j++)
11     scanf("%d",&map[i][j]);
12     scanf("%d",&m);
13     for(int i=1;i<=m;i++){
14         scanf("%d%d",&a,&b);
15         map[a][b]=map[b][a]=0;
16     }
17     for(int i=1;i<=n;i++) now[i]=map[1][i];
18     v[1]=1;k=n-1;now[0]=123456789;
19     while(k--){
20         a=0;
21         for(int i=1;i<=n;i++)
22         if(!v[i]&&now[i]<now[a]) a=i;
23         v[a]=1;ans+=now[a];
24         for(int i=1;i<=n;i++)
25         now[i]=min(now[i],map[a][i]);
26     }
27     printf("%d\n",ans);
28     return 0;
29 }