poj1258 prime最短路模板

#include<iostream>
#include<string>
#include<string.h>
const int
N=500;
using namespace std;
int map[N][N],a[120],n,k,i,j,z,vis[120];; //矩阵
int main(){
while(cin>>n){
int sum=0;
memset(a,0,sizeof(a));
memset(map,0,sizeof(map));
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) cin>>map[i][j];
for(j=1;j<=n;j++)
a[j]=map[1][j]; //更新其i j的距离//用第一个点更新其
vis[1]=1;//	put();
for(i=2;i<=n;i++){
int min=0x3f3f3f3f;
for(j=1;j<=n;j++)
//找第i后面的 最小的路径
if(min>a[j]&&a[j]>=0&&!vis[j])	min=a[k=j];//保存其村
vis[k]=1;sum+=min;//cout<<"路径为:"<<i<<"->"<<k<<endl;//因为加入了新的村庄 要更新新村庄与各路的最小值 比较原来表中的值
for(z=1;z<=n;z++) if(map[k][z]<a[z])	a[z]=map[k][z];//更新表
}
cout<<sum<<endl;
}
return 0;
}

最后

以上就是文静水壶为你收集整理的poj1258 prime最短路模板的全部内容，希望文章能够帮你解决poj1258 prime最短路模板所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。