Cod sursă (job #624804)

#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;
    for (int i = 1; i <= n; i++)
    {
        int nod = 0, dist = 2e9;
        for (int j = 1; j <= n; j++)
        {
            ///cout << d[j] << " ";
            if (dist > d[j] && viz[j] == 0)
            {
                nod = j;
                dist = d[j];
            }
        }
        viz[nod] = 1;
        sum += dist;
        for (auto j : h[nod])
            if (viz[j.second] == 0 && d[j.second] > j.first)
                d[j.second] = j.first;
    }
    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;
}