conquest.cc

#include <bits/stdc++.h>

using namespace std;

int bfs(map<int, set<int>>& M, unordered_map<int, size_t>& lookup) {
	priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
	set<int> visited;
	min_heap.push(0);

	int total{};
	while(!min_heap.empty()) {
		int top = min_heap.top(); min_heap.pop();
		total += lookup[top];
		visited.insert(top);
		
		set<int> neighbours = M[top];
		for(auto it = neighbours.begin(); it != neighbours.end(); ++it) {
			int neighbour = *it;
			if(visited.count(neighbour)) continue;
			min_heap.push(neighbour);
		}
	}
	return total;
}

int main() {
	int n, m;
	cin >> n >> m;

	map<int, set<int>> mat;

	unordered_map<int, size_t> lookup;

	for(int x{}; x < m; ++x) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		mat[u].insert(v);
		mat[v].insert(u);
	}
	for(int x{}; x < n; ++x) {
		int score;
		cin >> score;
		lookup[x] = score;
	}

	int res = bfs(mat, lookup);
	cout << res << endl;


	return 0;
}