为什么还是不对呢?
查看原帖
为什么还是不对呢?
592490
kesiyuan楼主2023/4/1 11:35

求助,为啥过不去呀

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5010,INF=0x3f3f3f3f;
int g[N][N];
int dist[N];
int n,m,x,y,z;
bool vis[N];

int Prim()
{
	memset(dist,0x3f,sizeof dist);
	
	int res=0;
	for (int i=0;i<n;i++)
	{
		int t=-1;
		for (int j=1;j<=n;j++)
		  if (!vis[j] && (t==-1 || dist[t]>dist[j]))
		    t=j;
		//取一个离集合最近的点 
		
		if (i && dist[t]==INF) return -1;
		//最近的点到集合的距离都是无穷花的话,那么就是不连通的 
		if (i) res+=dist[t];
		
		for (int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);
		//用这个点更新其他点到集合的距离 
		vis[t]=1;
	}
	//每次都是找到最小值,然后更新其他点,最后加到集合里面去 
	return res;
}

int main()
{
	scanf("%d%d",&n,&m);
	memset(g,0x3f,sizeof g);
	while (m--)
	{
		scanf("%d%d%d",&x,&y,&z);
		g[x][y]=g[y][z]=min(g[x][y],z);
	}
	int t=Prim();
	if (t==-1) printf("org");
	  else printf("%d",t);
	return 0;
}
2023/4/1 11:35
加载中...