当前位置:网站首页>AcWing 1140. Shortest network (minimum spanning tree)
AcWing 1140. Shortest network (minimum spanning tree)
2022-07-07 01:36:00 【Mr. Qiao Da】
AcWing 1140. The shortest network
Minimum spanning tree template
#include<bits/stdc++.h>
using namespace std;
const int N = 210;
int dist[N]; //dist It records the distance between this point and the connected block
int n, m;
int w[N][N];
bool st[N];
int prime(){
int res = 0;
memset(dist, 0x3f, sizeof dist);
dist[1] = 0; // Only the number in the initialized connected block is 1 The point of
for(int i = 1; i <= n; i ++ ){
int t = -1;
for(int j = 1; j <= n; j ++ ){
if(!st[j] && (t == -1 || dist[t] > dist[j])){
t = j;
}
}
res += dist[t];
st[t] = true;
for(int j = 1; j <= n; j ++ ){
dist[j] = min(dist[j], w[t][j]); //dist It records the distance between this point and the connected block , here t Is the outermost point in the connected block
}
}
return res;
}
int main()
{
cin>>n;
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= n; j ++ ){
cin>>w[i][j];
}
}
cout<<prime()<<endl;
return 0;
}
边栏推荐
猜你喜欢
随机推荐
[advanced C language] 8 written questions of pointer
域分析工具BloodHound的使用说明
编译命令行终端 swift
Today's question -2022/7/4 modify string reference type variables in lambda body
【C语言进阶篇】指针的8道笔试题
c语言—数组
Byte P7 professional level explanation: common tools and test methods for interface testing, Freeman
Send template message via wechat official account
THREE. AxesHelper is not a constructor
Spark TPCDS Data Gen
AcWing 1140. 最短网络 (最小生成树)
How to prevent overfitting in cross validation
C language - array
[chip scheme design] pulse oximeter
According to the analysis of the Internet industry in 2022, how to choose a suitable position?
Taro2.* applet configuration sharing wechat circle of friends
微信公众号发送模板消息
What does security capability mean? What are the protection capabilities of different levels of ISO?
js如何快速创建一个长度为 n 的数组
云呐|工单管理办法,如何开展工单管理