2022.2.16

10:00----10:30 13:00-----16:00 17:00---19:00

Today, I pushed the suitcase

tuixiangzi （c++）_bu_xiang_tutou The blog of -CSDN Blog

19:00---20:30

【 Templates 】 Minimum spanning tree

prim Solve the algorithm once

#include<bits/stdc++.h>
using namespace std;
#define inf 1e4+10
int dis[5009],v[5009],r[5009][5009],an,cnt,n,m;
int main()
{
	int i,x,y,z;
	cin>>n>>m;
	for(x=1;x<=n;x++)
	{
		for(y=1;y<=n;y++)
		{
			if(x==y)
			r[x][y]=0;
			else
			r[x][y]=inf;
		}
	}
	for(i=1;i<=m;i++)
	{
		cin>>x>>y>>z;
		r[x][y]=min(z,r[x][y]);
		r[y][x]=min(z,r[y][x]);// Undirected graph  
	}
	for(i=1;i<=n;i++)
	dis[i]=r[1][i];
	dis[1]=0;
	v[1]=1;
	while(cnt<n-1)
	{
		int min=inf,ans=-1;
		for(i=1;i<=n;i++)// Find the minimum distance value  
		{
			if(min>dis[i]&&v[i]==0)
			{
				min=dis[i];
				ans=i;
			}
		}
		v[ans]=1;
		cnt++;
		an+=dis[ans];
		for(i=1;i<=n;i++)// Update distance value  
		{
			if(v[i]==0&&dis[i]>r[ans][i])
			{
				dis[i]=r[ans][i];
			}	
		}
		
	} 
	int sign=0;
	for(i=1;i<=n;i++)
	{
		if(v[i]==0)
		{
		sign=1;
		printf("orz");
		break;
		}
	}
	if(sign==0)
	cout<<an;
	return 0;
} 

This code can only ac79, Three answers are out of time  

#include<bits/stdc++.h>
using namespace std;
#define inf 1e4+10
int dis[5009],v[5009],an,n,m;
struct node{
	int next;
	int end;
	int v;
}lu[200009];
int head[200009],cnt;
void add(int x,int y,int z)
{
	cnt++;
	lu[cnt].end=y;
	lu[cnt].v=z;
	lu[cnt].next=head[x];
	head[x]=cnt;
}
int main()
{
	int i,x,y,z,t=0;
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);// Undirected graph  
	}
	for(i=1;i<=n;i++)
	dis[i]=inf;
	dis[1]=0;
	v[1]=1;
	int ans=1;
	while(t<n-1)
	{
		int min=inf;
		v[ans]=1;
		for(i=head[ans];i!=0;i=lu[i].next)// Find the minimum distance value  
		{
			int b=lu[i].end,c=lu[i].v;
			if(dis[b]>c&&v[b]==0)
			{
				dis[b]=c;
			}
		}
		for(i=1;i<=n;i++)// Update distance value  
		{
			if(v[i]==0&&min>dis[i])
			{
				min=dis[i];
				ans=i;
			}	
		}
		an+=dis[ans];
		t++;
	} 
	int sign=0;
	for(i=1;i<=n;i++)
	{
		if(v[i]==0)
		{
		sign++;
		}
	}
	if(sign==1)
	cout<<an;
	else
	printf("orz");
	return 0;
}