提供一组数据
输入：
```
5 18
2 4 276
3 3 435
3 4 608
2 4 860
1 2 318
1 3 547
5 4 419
2 5 98
1 5 460
5 3 399
3 5 240
3 2 733
3 3 903
4 2 909
5 2 206
3 4 810
2 1 115
2 3 419
```
正确输出:
```
729
```
俺の输出:
```
1172
by Bigfish_ @ 2022-07-27 21:58:13
《Prime》
by Zvelig1205 @ 2022-07-27 22:03:00
@[极冬寒雪](/user/413020) 《质数算法》
by char_cha_ch @ 2022-07-27 22:04:45
@[极冬寒雪](/user/413020) doge
by Bigfish_ @ 2022-07-27 22:07:38
救救孩子吧，明天就要讲这道题了
by Bigfish_ @ 2022-07-27 22:08:08
OI-WIKI
by FWT__FFT @ 2022-07-27 22:39:51
=w=
by Bigfish_ @ 2022-07-27 22:53:08
AC了。。
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,m,minn[5010],f[5005][5005],u,v,minmax1=0;
int l=0;//计数器
long long MST=0;
bool b[5010];//蓝白点
inline int read()
{
int x=0,j=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') j=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*j;
}
int main()
{
n=read();m=read();
for(int t=1;t<=n;++t)//初始化f
for(int i=1;i<=n;++i)
f[t][i]=INT_MAX;
if(m<n-1)//特判优化？
{
printf("orz");
return 0;
}
for(int t=0;t<=n;++t)//初始化minn
minn[t]=INT_MAX;
for(int t=1;t<=m;++t)
{
int x=read(),y=read(),z=read();
if(f[x][y]!=0&&f[x][y]<=z) ;//不赋值
else
{
f[x][y]=z;
f[y][x]=z;
}
}
minn[1]=0;
b[1]=0;//标记为蓝点=w=
for(int t=1;t<=n;++t)//枚举所有的点
{
minmax1=0;
for(int i=1;i<=n;++i)//找距离最小的蓝点
{
if(b[i]==0&&minn[i]<minn[minmax1])
{
minmax1=i;
}
}
if(minmax1==0) break;//找不到代表图不连通,优化？
b[minmax1]=1;//标记为白点
MST+=minn[minmax1];
++l;//记录白点个数
for(int i=1;i<=n;++i)
{
if(b[i]==0&&minn[i]>f[minmax1][i])//蓝点i到现在所有白点 的最小距离
{
minn[i]=f[minmax1][i];//更新minn数组
}
}
}
if(l==n)
printf("%d",MST);
else
printf("orz");
return 0;
}
by Bigfish_ @ 2022-07-27 23:13:15