AcWing 858. Prim算法求最小生成树
原题链接
简单
作者:
HUE菜鸡联盟
,
2021-12-06 20:17:34
,
所有人可见
,
阅读 126
#include<bits/stdc++.h>
#define int long long
#define for0(x,n) for(int x=0;x<n;x++)
#define for1(x,n) for(int x=1;x<=n;x++)
int n,m,ans,t;
const int tt=1e3+10,mod=1e6+7,INF=0x7f7f7f7f;
using namespace std;
int cost[tt][tt];
int mincost[tt];
bool used[tt];
int V,E;
int prim()
{
for(int i=1;i<=V;i++)
{
mincost[i]=INF;
used[i]=false;
}
mincost[1]=0;
int res=0;
while(true)
{
int v=-1;
for(int u=1;u<=V;u++)
{
if(!used[u]&&(mincost[u]<mincost[v]))v=u;
}
if(v==-1)break;
used[v]=true;
res+=mincost[v];
// cout<<res<<endl;
for(int u=1;u<=V;u++)
{
mincost[u]=min(mincost[u],cost[v][u]);
}
if(abs(res)>5000000)return 0;
}
return res;
}
signed main()
{
memset(cost,0x7f,sizeof(cost));
cin>>V>>E;
for1(i,E)
{
int from,to,spend;
cin>>from>>to>>spend;
cost[from][to]=min(spend,cost[from][to]);
cost[to][from]=cost[from][to];
}
// cout<<prim();
prim()==0?cout<<"impossible":cout<<prim();
}