hahaboluo @ 2022-07-21 15:04:06
#include<bits/stdc++.h>
using namespace std;
const int N=5500,INF=0x3f3f3f3f;
int n,m,dist[N],g[N][N];
bool st[N];
int prim()
{
memset(dist,0x3f,sizeof dist);
long long ans=0;
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!st[j] && (t==-1 || dist[t]>dist[j]))
t=j;
}
if(i && dist[t]==INF)
return INF;
if(i)
ans+=dist[t];
st[t]=true;
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],g[t][j]);
}
return ans;
}
int main()
{
cin>>n>>m;
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
long long t=prim();
if(t==INF)
cout<<"orz";
else
cout<<t;
return 0;
}
by henrywyh @ 2022-07-21 15:23:12
说错了是你的g[t][j]在比较的时候
dist[j]=min(dist[j],g[t][j]);
都是0,导致dist后面全是0,ans累加的也都是0
by hahaboluo @ 2022-07-22 11:47:34
@henrywyh 厉害厉害 多谢