题目传送门：

题目大意：

要修公路，输入一个n，表示n个村庄。接着输入n*n的矩阵，该图的邻接矩阵，然后输入一个q 接下来的q行

每行包含两个数a，b，表示a、b这条边联通，就是已经有公路不用修了，要让所有村庄联通在一起问：修路最小代价？

分析：

根据题目输入构造邻接矩阵，然后把已经联通的村庄的距离设置为0，表示不用在修这条公路。在用新的邻接矩阵跑prim就可以了

代码：

#include
     
      #include
      
       #include
       
        using namespace std;const int INF=0x3f3f3f3f;const int MAX=150;int n,map[MAX][MAX],q;int dist[MAX];bool vis[MAX];struct rood{    int st,en;}ro[MAX*(MAX+1)+10];int prim(){    for(int i=0;i<=n;i++)    {        dist[i]=INF;        vis[i]=false;    }    dist[1]=0;    int min,pos,ans=0;    for(int i=1;i<=n;i++)    {        min=INF;        for(int j=1;j<=n;j++)        {            if(!vis[j]&&min>dist[j])            {                min=dist[j];                pos=j;            }        }        vis[pos]=true;        ans+=min;         for(int j=1;j<=n;j++)        {            if(!vis[j]&&dist[j]>map[pos][j])            {                dist[j]=map[pos][j];            }        }    }    return ans;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)            scanf("%d",&map[i][j]);                scanf("%d",&q);    for(int i=0;i