Ice_cream’s world III

2 1
0 1 10

4 0

10

impossible

#include<stdio.h>
#include<string.h>
int v[10010],map[10010][10010];
#define inf 0xfffffff;
int main()
{
	int n,m,i,j,a,b,c;
	while(~scanf("%d%d",&n,&m))
	{
		int sum=0;
		memset(v,0,sizeof(v));
		for(i=0;i<n;i++)//初始化 
		{
			for(j=0;j<n;j++)
			{
				map[i][j]=inf;
			}
		}
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			if(c<map[a][b])//判断是否是重边，要是起点终点都相同的时候，就去权值最小的作为两个顶点间的距离即是权值 
			map[a][b]=map[b][a]=c;
		}
		v[0]=1;
		int flag;
		for(i=1;i<n;i++)
		{
			int min=inf;
			flag=-1;
			for(j=0;j<n;j++)
			{
				if(!v[j]&&map[0][j]<min)
				{
					min=map[0][j];
					flag=j;
				}
			}
			if(flag==-1)
			break;
			v[flag]=1;
			sum+=map[0][flag];
			for(j=0;j<n;j++)
			{
				if(!v[j]&&map[0][j]>map[flag][j])
				map[0][j]=map[flag][j];
			}
		}
		if(flag==-1)
		printf("impossible\n\n");
		else
		printf("%d\n\n",sum);
	}
	return 0;
}

#include<stdio.h>
#include<algorithm>
using namespace std;
struct node{
	int a,b,c;
}s[10010];
int father[10010];
int find(int r)
{
	return r==father[r]?r:find(father[r]);
}
int cmp(node x,node y)
{
	return x.c<y.c;
}
int main()
{
	int n,m,i,j;
	while(~scanf("%d%d",&n,&m))
	{
		for(i=0;i<n;i++)//初始化 
		{
			father[i]=i;
		}
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c);
		}
		sort(s,s+m,cmp);//求的是最小的生成树，所以按照权值 增序排列 
		int count=0,sum=0;
		for(i=0;i<m;i++)//一共有m条边，所有循环到m 
		{
			int fa=find(s[i].a);
			int fb=find(s[i].b);
			if(fa!=fb)
			{
				father[fa]=fb;
				sum+=s[i].c;
				count++;//除了这一点都是克鲁斯卡尔算法模板 
			}
		}
		if(count!=n-1)//是否是n-1条边 即建立了一个满足条件的最小生成树 
		{
			printf("impossible\n\n");
		}
		else
		printf("%d\n\n",sum);
	}
	return 0;
}