Cod sursă (job #720084)

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

const int MAXN = 1005;
const int INF = numeric_limits<int>::max(); // Updated initialization

int dist[MAXN], n, m, k;
vector<vector<pair<int, int> > > adj(MAXN);

void Dijkstra(int s) {
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    fill(dist, dist + MAXN, INF); // Updated initialization
    pq.push(make_pair(0, s));
    dist[s] = 0;
    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (d > dist[u])
            continue;
        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i].first;
            int w = adj[u][i].second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
}

int main() {
    ifstream fin("zapada.in");
    ofstream fout("zapada.out");
    fin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        fin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }
    Dijkstra(1);
    int ans = 0;
    for (int i = 2; i <= n; i++) {
        ans += dist[i];
    }
    fout << ans << '\n';
    for (int i = 0; i < k; i++) {
        int u, v, w;
        fin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
        dist[u] = min(dist[u], w); // Update distance values for affected nodes
        dist[v] = min(dist[v], w);
        ans = 0;
        for (int j = 2; j <= n; j++) {
            ans += dist[j];
        }
        fout << ans << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}