首页 > 代码库 > POJ2421 Constructing Roads
POJ2421 Constructing Roads
Constructing Roads
这道题很水,就是一个裸的最小生成树,最不过把已经连接的节点的值再设为0。
代码:
1 #include<cstdio> 2 #include<cstring> 3 #define N 1010 4 int dis[N][N],minn[N],n,m,a,b; 5 bool u[N]; 6 int main(){ 7 scanf("%d",&n); 8 for(int i=1;i<=n;++i) 9 for(int j=1;j<=n;++j) 10 scanf("%d",&dis[i][j]); 11 scanf("%d",&m); 12 for(int i=1;i<=m;++i){ 13 scanf("%d%d",&a,&b); 14 dis[a][b]=0; 15 dis[b][a]=0; 16 } 17 memset(minn,0x7f,sizeof(minn)); 18 minn[1]=0; 19 memset(u,1,sizeof(u)); 20 for(int i=1;i<=n;++i){ 21 int k=0; 22 for(int j=1;j<=n;++j) 23 if(u[j]&&(minn[j]<minn[k])) 24 k=j; 25 u[k]=0; 26 for(int j=1;j<=n;j++) 27 if(u[j]&&(dis[k][j]<minn[j])) 28 minn[j]=dis[k][j]; 29 } 30 int total=0; 31 for(int i=1;i<=n;++i) 32 total+=minn[i]; 33 printf("%d",total); 34 return 0; 35 }
POJ2421 Constructing Roads
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。