HDOJ1102 修路问题（最小生成树Prim）

题目：

1102	Constructing Roads

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

#define M 100
#define MAX 9999

int map[M][M],visited[M],adjset[M];
int n,p,len;

void ReadMap();

void main()
{
    int i,j,nlen,nid;
    while (scanf("%d",&n)!=EOF)
    {
        //读取地图
        ReadMap();
        //初始化
        memset(visited,0,sizeof(visited));
        visited[0] = 1;
        len = 0;
        for (i=0;i<n;i++)    adjset[i] = map[i][0];
        //Begin
        for (i=1;i<n;i++)
        {
            //找到下一条符合条件的点
            nlen = MAX;
            for (j=0;j<n;j++)
            {
                if (!visited[j] && adjset[j]<nlen)
                {
                    nlen = adjset[j];
                    nid = j;
                }
            }
            //访问找到的那个点
            len += nlen;
            visited[nid] = 1;
            //更新邻接距离
            for (j=0;j<n;j++)
            {
                if (!visited[j] && map[j][nid]<adjset[j])
                {
                    adjset[j] = map[j][nid];
                }
            }
        }
        cout<<len<<endl;
    }
}

void ReadMap()
{
    int i,j,a,b;
    for (i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
        {
            cin>>map[i][j];
        }
    }
    cin>>p;
    for (i=0;i<p;i++)
    {
        cin>>a>>b;
        map[a-1][b-1] = map[b-1][a-1] = 0;
    }
}