图论入门，Prim算法求最小生成树代价，HDOJ 1879 继续畅通工程

HDOJ 1879 继续畅通工程，HDOJ 1233还是畅通工程类似；HDOJ 图论相关题目：
1869 六度分离
1863 畅通工程
1875 畅通工程续
1301 Jungle Roads
2066 一个人的旅行
2112 HDU Today
……

#include<iostream>
using namespace std;

#define N 1000
#define MaxVal INT_MAX
//INT_MAX是最大整数，当吃不准最大边值时使用
//邻接矩阵，mat[i][j]的值为MaxVal表示i到j无边，否则为i到j边上的权值
int mat[N][N];

int visited[N]; //辅助数组，各顶点访问标记

//辅助数组，dist[i]保存以i为终点的边的最小权值，扫描本数组可以判断是否连通图
int dist[N];  

int n; //顶点数

//找以未访问过的顶点为终点的最小权值的边，找到返回该顶点编号，否则返回-1
int minVertex() 
{
    int i, next=-1, minDist=MaxVal;
  
    for (i=0;i<n;i++)
    {
        if (visited[i]==1) continue; //若该顶点已访问过则结束本次循环
        
        if (minDist>dist[i]) //若以i为终点的边权值更小则更新
		{
			minDist=dist[i];
			next=i; 
		}
    }

    return next;
}

//从顶点s开始求连通图的最小生成树的代价
int Prim(int s) 
{
    int i, next, cost=0;

    for(int i=0;i<n;i++) 
    {
        dist[i]=mat[s][i];
    }
    
    visited[s]=1;

    while(true) //连通图做n-1次循环
    {
        next=minVertex();
        if (next==-1) break; 

        visited[next]=1; //找到以next为终点的边
        cost += dist[next]; //亦可在本循环后累加dist数组

        for (i=0; i<n; i++)//修正各未访问过的顶点为终点的边的权值 
        {
            if (visited[i]==0 && mat[next][i]<dist[i]) //Dijkstra算法主要此处有区别
            {
                dist[i]=mat[next][i];
            }
        }
    }

    return cost;
}

bool run()
{
    int i, j, total, x, y, w, s;

    scanf("%d",&n);
    if(n==0) return 0;

    for(i=0; i<n; i++) //初始化
    {
        visited[i]=0;

        for(j=0;j<n;j++)
        {
            mat[i][j]=MaxVal;
        }
        
        mat[i][i]=0;
    }

    total=n*(n-1)/2;//先算出，可以提高一点时间效率

    for(int i=0;i<total;i++) //输入边
    {
        scanf("%d%d%d%d",&x,&y,&w,&s);
        if (s==1) w=0; 
        x--;
        y--;
        mat[x][y]=w;
        mat[y][x]=w;
    }

    printf("%d\n", Prim(0) );

    return 1;
}

int main()
{
   while(run());  
   return 0;
}