求调
查看原帖
求调
930277
Benty楼主2025/7/3 14:22
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10, M = 0x3f3f3f3f;

int G[N][N], dist[N];
int n, m, res;
bool vis[N]; 

void prim() {
	dist[1] = 0;
    vis[1] = true;

    for (int i = 2; i <= n; i ++) 
        dist[i] = min(dist[i], G[1][i]);

    for (int i = 2; i <= n; i ++) {
        int temp = M, t = -1;
        for (int j = 2; j <= n; j ++) 
            if (!vis[j] && dist[j] < temp) 
                temp = dist[j], t = j;
        if (t == -1) { res = M; return; }
        vis[t] = true;
        res += dist[t];
        for (int j = 2; j <= n; j ++) 
            dist[j] = min(dist[j], G[t][j]);
    }
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= n; j ++) G[i][j] = M;
		dist[i] = M;
	}
	
	for (int i = 1; i <= m; i ++) {
		int x, y, w; scanf("%d %d %d", &x, &y, &w);
		G[x][y] = G[y][x] = w;
	}
	
	prim();
	if (res == M) printf("orz");
	else printf("%d", res); 
	
	return 0; 
}
2025/7/3 14:22
加载中...