Cod sursă (job #749609)

#include <fstream>
#include <queue>
#include <vector>
using namespace std;

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

vector< vector< pair<int, int> > > G;
int N,M,K;
priority_queue< pair<int, int>, vector< pair<int, int> >, std::greater< pair<int, int> > > PQ;
short visited[100005];
int total_cost = 0;

void solve()
{
    total_cost = 0;
    for(int i = 1; i <= N; i++)
        visited[i] = 0;
    while(!PQ.empty()) PQ.pop(); // clear queue
    PQ.emplace(0, 1);
    while(!PQ.empty())
    {
        auto x = PQ.top();
        PQ.pop();
        if(visited[x.second])
            continue; // already visited and added to APM
        visited[x.second] = 1;
        total_cost += x.first;
        for(const auto& v : G[x.second])
        {
            if(!visited[v.first])
            {
                PQ.emplace(v.second, v.first);
            }
        }
    }
    fout << total_cost << endl;
}

int main()
{
    fin >> N >> M >> K;
    G.resize(N + 1);
    int a, b, c;
    while(M--)
    {
        fin >> a >> b >> c;
        G[a].emplace_back(b, c);
        G[b].emplace_back(a, c);
    }
    solve();
    while(K--)
    {
        fin >> a >> b >> c;
        G[a].emplace_back(b, c);
        G[b].emplace_back(a, c);
        solve();
    }
    return 0;
}