7-3 修建道路

N个村庄，从1到N编号，现在请您兴建一些路使得任何两个村庄彼此连通。我们称村庄A和B是连通的，当且仅当在A和B之间存在一条路，或者存在一个存在C，使得A和C之间有一条路，并且C和B是连通的。

已知在一些村庄之间已经有了一些路，您的工作是再兴建一些路，使得所有的村庄都是连通的，并且兴建的路的长度是最小的。

输入格式:

第一行是一个整数N（3<=N<=100），代表村庄的数目。后面的N行，第i行包含N个整数，这N个整数中的第j个整数是第i个村庄和第j个村庄之间的距离，距离值在[1,1000]之间。

然后是一个整数Q(0<=Q<=N*(N+1)/2)。后面给出Q行，每行包含两个整数a和b（1<=a<b<=N），表示在村庄a和b之间已经兴建了路。

输出格式:

输出一行仅有一个整数，表示为使所有的村庄连通需要新建公路的长度的最小值。

输入样例:

3
0 990 692
990 0 179
692 179 0
1
1 2

输出样例:

179
通过分析，我使用了构建最小生成树的Prim算法，代码如下

#include <bits/stdc++.h>
#define N 105
using namespace std;
typedef struct
{
    int vexs[N];
    int arcs[N][N];
    int vexnum, arcnum;
} Graph;//图的结构体
int D[N] = {0} ;
int visited[N] = {0} ; 
void Create_G(Graph &G)//创建图，输入结点和个节点的距离
{
    cin >> G.vexnum ;
    int i,j;
    int m=G.vexnum;
    for(i = 1; i <= m; ++i)
    {
        for(j = 1; j <=m ; ++j)
        {
            cin >> G.arcs[i][j];
        }
    }
    int n;
    cin >> n ;
    for( i = 0 ; i < n ; ++i)
    {
        int a,b;
        cin >> a >> b ;
        G.arcs[a][b] = G.arcs[b][a] = 0;//已建成的置距离为0
        visited[a]=1;
        visited[b]=1;//标记为已访问
    }
}

int Prim_Road(Graph G)//prim算法实现
{
    int i,j,k=1,mi;
    int cost = 0;
    int nums = G.vexnum;
    for(i = 1 ; i <= nums; ++i)
    {
        D[i] = G.arcs[1][i];
        visited[i] = 0 ;
    }
    D[1] = 0 ;
    visited[1] = 1 ;//初始化数组D[]存储权值，数组visited[]标记已被访问
    for(i = 1; i <= nums; ++i)
    {
        mi=INT_MAX;
       
        for(j=1;j<=nums;++j)//寻找权值最小的边，且未被访问，记录其下标为k
        {
           if(D[j]<mi&&!visited[j])
           {
            mi=D[j];
            k=j;
           }
        }
        cost += D[k]; //计算所需距离
        D[k]=0;//将k点到原点的距离置为0
        visited[k] = 1;//将k点标记为已被访问
        for(j = 1 ; j <= nums; ++j)
        {
            if(G.arcs[k][j] < D[j] && !visited[j])
            {
                D[j] = G.arcs[k][j];//更新数组D[]
            }
        }
    }
    return cost;
}
int main()
{
    Graph G;
    Create_G(G);
    cout << Prim_Road(G) << endl;
    return 0;
}