记录编号	164418	评测结果	AAAAAAAAAA
题目名称	最优布线问题	最终得分	100
用户昵称	作死大王	是否通过	通过
代码语言	C++	运行时间	0.818 s
提交时间	2015-05-30 16:18:43	内存使用	8.91 MiB

#include<fstream>
using namespace std;
ifstream fin("wire.in"); 
ofstream fout("wire.out");

//map数组用来存储图 
int map[1501][1501];
//d数组用来存到达i点的最短路，0表示不存在路，-1表示该点已被访问
int d[1501]; 
int n,sum=0; //n用来表示计算机的数目，sum用来累计最短路之和

int min(int c[],int *m)
{
    int min=888888888;
    int i;
    for(i=1;i<=n;i++)
    {
        if(c[i]>0){ 
            if(c[i]<min){
             min=c[i];
            *m=i;
            }
        } 
    }
   
    return min;
}

int main(){
    fin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            fin>>map[i][j];
        }
    }
    
    //开始生成最小生成树 
    //1初始化d
    d[1]=-1; 
    for(int i=2;i<=n;i++){
        //写程序，此处给数组d赋值
         d[i]=map[1][i] ;
    }
    
    //2开始构造树
    int co=1,mi,p;//co用来计数，表示已选取了co个顶点；mi表示最小值，p表示最小值所连接顶点 
    for(;co<n;co++){
        //写程序，从d里面找最小的
        mi=::min(d,&p);
        sum+=mi;
        d[p]=-1;
        //写程序，更新d的值
        for(int i=1;i<=n;i++)
        {
            if(d[i]==0) d[i]=map[p][i];
            if(d[i]!=-1)d[i]=map[p][i]<d[i]?map[p][i]:d[i];
        }
    }
    
    fout<<sum<<endl;
    return 0;
}