标签：0x3f prim cout int 最小 st 模板
858. Prim算法求最小生成树 - AcWing题库
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m,k;
int d[N];
bool st[N];
int g[N][N];
void prim()
{
memset (d,0x3f,sizeof d);
int res=0;//长度
d[1]=0;//作为头
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
if(!st[j]&&(d[t]>d[j]||t==-1))
t=j;
if(d[t]==0x3f3f3f3f) //如果最小边是0x3f那么就不会连通
{
cout<<"impossible";
return;
}
res+=d[t];
st[t]=1;
for(int j=1;j<=n;j++)
{
if(d[j]>g[t][j]&&!st[j])//注意是g[t][j]是点到集合的最短距离
{
d[j]=g[t][j];
}
}
}
cout<<res;
return ;
}
signed main()
{
memset(g,0x3f,sizeof g);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
prim();
}
标签：0x3f,
prim,
cout,
int,
最小,
st,
模板
From： https://blog.csdn.net/hui_le4/article/details/140331889