【HPU】[1736]老王修马路(二)

【HPU】[1736]老王修马路(二)最小生成树问题 没什么弯 需要注意的是有可能无法连通 include stdio h include algorithm using namespace std int main int T scanf d amp T while T int dis 120 algorithm stdio h

大家好,我是讯享网,很高兴认识大家。

这里写图片描述
讯享网

最小生成树问题
没什么弯
需要注意的是有可能无法连通

#include<stdio.h> #include<algorithm> using namespace std; int main() { int T; scanf("%d",&T); while(T--) { int dis[120]; int e[120][120]; bool flag[120]; int inf=; int n,m; scanf("%d %d",&n,&m); for(int i=1; i<=n; i++) { dis[i]=inf; flag[i]=false; } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { e[i][j]=inf; } } while(m--) { int i,j,t; scanf("%d %d %d",&i,&j,&t); if(e[i][j]>t) { e[i][j]=t; e[j][i]=t; } } int sum=0; dis[1]=0; bool x=true; while(true) { int v=-1; for(int u=1; u<=n; u++) { if(!flag[u]&&(v==-1||dis[u]<dis[v])) v=u; } if(v==-1) break; else { flag[v]=true; if(dis[v]==inf) { x=false; printf("Wrong\n"); break; } else sum+=dis[v]; for(int u=1; u<=n; u++) { dis[u]=min(dis[u],e[v][u]); } } } if(x) printf("%d\n",sum); } return 0; } 

讯享网

题目地址:【HPU】[1736]老王修马路(二)

小讯
上一篇 2025-03-11 20:16
下一篇 2025-04-10 16:33

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/79709.html