Участник:AlinaS/MST

Материал из DISCOPAL
Перейти к: навигация, поиск

Задача https://www.spoj.com/problems/MST/

Компилятор C++ (gcc 8.3)

#include<bits/stdc++.h>
using namespace std;
 
static const int MAXN = 1e6+1;
 
using Neighbor = pair<int, int>;
using Graph = vector<vector<Neighbor>>;
 
long long get_mst_weight(const Graph &g) {
    vector<bool> used(g.size(), false);
    vector<int> key(g.size(), MAXN);
    set<pair<int, int>> q;
 
    q.insert(make_pair(0, 0));
    key[0] = 0;
    long long w = 0;
 
    while(!q.empty()) {
        int cur = (q.begin())->second;
        q.erase(q.begin());
        used[cur] = true;
        for (auto next : g[cur]) {
            if (!used[next.first] && (key[next.first] > next.second)) {
                q.erase(make_pair(key[next.first], next.first));
                long long delta = 0;
                if (key[next.first] < MAXN)
                    delta = key[next.first];
                w += (next.second - delta);
                key[next.first] = next.second;
                q.insert(make_pair(key[next.first], next.first));
            }
        }
    }
 
    return w;
}
 
int main() {
    int n = 0, m = 0;
    cin >> n >> m;
    Graph g(n);
    for (int i = 0; i < m; i++) {
        int out = 0, in = 0, w = 0;
        cin >> out >> in >> w;
        g[out-1].push_back(make_pair(in-1, w));
        g[in-1].push_back(make_pair(out-1, w));
    }
    cout << get_mst_weight(g) << endl;
    return 0;
}