#8#9#10#13求条
查看原帖
#8#9#10#13求条
1403683
Super_Ygg_Dahlia楼主2024/12/11 19:43
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll M=3005;
ll n,m;
ll g[M][M];
ll dist[M];
bool st[M];
ll Prim(){
	int res=0;
	memset(dist,0x3f,sizeof(dist));
	dist[1]=0; 
	for(ll i=0;i<n;i++){
		int t=-1;
		for(ll j=1;j<=n;j++){
			if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;
		}
		st[t]=true;
		if(dist[t]==0x3f3f3f3f) return 0x3f3f3f3f;
		res+=dist[t];
		for(int j=1;j<=n;++j)dist[j]=min(dist[j],g[t][j]);
	}
	return res;
}
int main(){
	ll i;
	scanf("%lld%lld",&n,&m);
	memset(g,0x3f,sizeof(g));
	for(i=0;i<m;i++){
		ll x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		g[x][y]=g[y][x]=min(g[x][y],z);
	}
	ll prim=Prim();
	if(prim==0x3f3f3f3f) printf("orz");
	else cout<<prim;
	return 0;
}

必关 谢谢

2024/12/11 19:43
加载中...