Prim37分求助
查看原帖
Prim37分求助
218180
lighthouse楼主2021/11/14 11:15
#include <bits/stdc++.h>

#define INF 10001

using namespace std;

int dis[5005];

int a[5005][5005];

bool vis[5005];

int main(){
	int n, m, mst = 0, tot = 0;
	cin >> n >> m;
	memset(a, 0x7f, sizeof(a));
	for(int i = 1;i <= n;i++){
		dis[i] = INF;
	}
	for(int i = 1;i <= m;i++){
		int x, y, z;
		cin >> x >> y >> z;
		a[x][y] = min(a[x][y], z);
		a[y][x] = min(a[y][x], z);
	}
	dis[1] = 0;
	for(int i = 1;i <= n;i++){
		int minn = INF, t = 1;
		for(int j = 1;j <= n;j++){
			if(vis[j] == 0 && dis[j] < minn){
				minn = dis[i];
				t = j;
			}
		}
		if(vis[t] == 1)
			continue;
		vis[t] = 1;
		for(int j = 1;j <= n;j++){
			if(vis[j] == 0 && a[t][j] < dis[j]){
				dis[j] = a[t][j];	
			}
		}
	}
	for(int i = 1;i <= n;i++){
		if(dis[i] == 10001) tot++;
		else mst += dis[i];
	}
	if(tot != 0) cout << "orz";
	else cout << mst;
	return 0;
}

WA #2 #3 #4 #5 #6 #7 #8 #9 #10 求调谢谢

2021/11/14 11:15
加载中...