Cod sursă (job #624803)

#include <bits/stdc++.h>

using namespace std;

ifstream fin ("zapada.in");
ofstream fout ("zapada.out");

int n , k , m, d[10005], viz[10005];


vector <pair <int, int> > h[10005];
set <pair <int ,int> > S;

void MSP ()
{
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        d[i] = 2e9;
        viz[i] = 0;
    }
    d[1] = 0;
    S.insert({0, 1});
    for (int i = 1; i <= n; i++)
    {
        while (viz[S.begin() -> second] && S.size())
            S.erase(S.begin());
        int nod = S.begin() -> second;
        int dist = S.begin() -> first;
        viz[nod] = 1;
        sum += dist;
        for (auto j : h[nod])
            if (viz[j.second] == 0 && d[j.second] > j.first)
            {
                S.erase({d[j.second], j.second});
                d[j.second] = j.first;
                S.insert({d[j.second], j.second});
            }
    }
    while (S.size())
        S.erase(S.begin());
    fout << sum << "\n";
}

void Solve ()
{
    MSP();
    for (int i = 1; i <= k; i++)
    {
        int x, y , c;
        fin >> x >> y >> c;
        h[x].push_back({c,y});
        h[y].push_back({c,x});
        MSP();
    }
}

int main()
{
    fin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
    {
        int x , y, c;
        fin >> x >> y >> c;
        h[x].push_back({c, y});
        h[y].push_back({c, x});
    }
    Solve();
    return 0;
}