Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <iostream>
- #include <vector>
- #include <set>
- int main() {
- std::fstream filein("spantree2.in");
- unsigned short int n;
- filein >> n;
- std::vector < std::pair<unsigned short int ,int> > g[n];
- std::vector<int> min_e (n, 100002);
- bool used[n];
- for (int i = 0; i < n; ++i) {
- used[i] = false;
- }
- long long int result = 0;
- int m, weight;
- filein >> m;
- unsigned short int vert1, vert2;
- for (int i = 0; i < m; ++i) {
- filein >> vert1 >> vert2 >> weight;
- g[vert1 - 1].emplace_back(std::make_pair (vert2 - 1, weight));
- g[vert2 - 1].emplace_back(std::make_pair (vert1 - 1, weight));
- }
- std::set < std::pair<int,unsigned short int> > q;
- q.insert (std::make_pair (0, 0));
- for (int i = 0; i < n; ++i) {
- result += q.begin()->first;
- unsigned short int v = q.begin()->second;
- used[v] = true;
- q.erase (q.begin());
- for (size_t j=0; j<g[v].size(); ++j) {
- int to = g[v][j].first,
- cost = g[v][j].second;
- if (cost < min_e[to] && !used[to]) {
- q.erase (std::make_pair (min_e[to], to));
- min_e[to] = cost;
- q.insert (std::make_pair (min_e[to], to));
- }
- }
- }
- std::ofstream fileout("spantree2.out");
- fileout << result;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement