prim求条(玄关)
查看原帖
prim求条(玄关)
1384608
kkksc_QAQ楼主2025/7/26 00:18
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n, m;
	cin >> n >> m;
	vector<vector<int>> g(n + 1, vector<int>(n + 1, 1e9));
	while(m--){
		int x, y, c;
		cin >> x >> y >> c;
		g[x][y] = c;
		g[y][x] = c;
	}
	vector<bool> tree(n + 1, false);
	vector<int> mindis(n + 1, 1e9);
	for(int i = 1; i < n; i++){
		int id = 1, mind = INT_MAX;
		for(int j = 1; j <= n; j++){
			if(mindis[j] < mind && !tree[j]){
				id = j, mind = mindis[j];
			}
		}
		tree[id] = true;
		for(int j = 1; j <= n; j++){
			if(g[id][j] < mindis[j] && !tree[j]){
				mindis[j] = g[id][j];
			}
		}
	}
	int ans = 0;
	for(int i = 2; i <= n; i++){
		if(mindis[i] == 1e9){
			cout << "orz";
			return 0;
		}
		ans += mindis[i];
	}
	cout << ans;
	return 0;
}

30pts

2025/7/26 00:18
加载中...