Cod sursă (job #144268)

/*
 * Vlad Ionescu - Universitatea Politehnica Bucuresti
 */
#include <iostream>
#include <algorithm>
#include <fstream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
using namespace std;
#define maxn 300300
#define inf 999999999

int N, M, K, Q;

int dist[maxn], height[maxn], father[maxn], cup[maxn];
vector< pair<int, int> > G[maxn];

vector< pair<int, pair<int, int> > > times;

queue<int> q;
bool inqueue[maxn];

void bellmanford() {
    int nod, vec, cost;

    while(!q.empty()) {
        nod = q.front(); q.pop();
        inqueue[nod] = false;

        for(int i=0; i<G[nod].size(); i++) {
            vec = G[nod][i].first;
            cost = G[nod][i].second;

            if(dist[vec] > dist[nod] + cost) {
                dist[vec] = dist[nod] + cost;

                if(!inqueue[vec]) {
                    inqueue[vec] = true;
                    q.push(vec);
                }
            }
        }
    }
}

void computetimes() {
    int vec, cost;

    for(int i=1; i<=N; i++) {
        for(int j=0; j<G[i].size(); j++) {
            vec = G[i][j].first;
            cost = G[i][j].second;

            if(vec <= i) continue;

            times.push_back( make_pair(min(dist[i], dist[vec]), make_pair(i, vec)) );
        }
    }
}

int getcc(int nod) {
    while(nod != father[nod]) {
        nod = father[nod];
    }

    return nod;
}

void unite(int cc1, int cc2, int t) {
    if(height[cc1] > height[cc2]) {
        father[cc2] = cc1;
        cup[cc2] = t;
    }
    else {
        father[cc1] = cc2;
        cup[cc1] = t;

        if(height[cc1] == height[cc2]) {
            height[cc2] ++;
        }
    }
}

void computedisjointset() {
    sort(times.begin(), times.end());

    int x, y, t;
    int ccx, ccy;

    for(int i=times.size()-1; i>=0; i--) {
        x = times[i].second.first;
        y = times[i].second.second;
        t = times[i].first;

        ccx = getcc(x);
        ccy = getcc(y);

        if(ccx != ccy) {
            unite(ccx, ccy, t);
        }
    }
}

int getheight(int nod) {
    int h = 0;

    while(nod != father[nod]) {
        h ++;

        nod = father[nod];
    }

    return h;
}

int query(int nod1, int nod2) {
    int min_edge_cost = inf;

    int h1 = getheight(nod1);
    int h2 = getheight(nod2);

    if(nod1 == nod2) {
        return dist[nod1];
    }

    while(nod1 != nod2) {
        if(h1 > h2) {
            min_edge_cost = min(min_edge_cost, cup[nod1]);

            nod1 = father[nod1];
            h1 --;
        }
        else {
            min_edge_cost = min(min_edge_cost, cup[nod2]);

            nod2 = father[nod2];
            h2 --;
        }
    }

    return min_edge_cost;
}

int main() {
    fstream f1, f2;

    f1.open("termite.in", ios::in);
    f2.open("termite.out", ios::out);

    f1 >> N >> M >> K >> Q;

    for(int i=1; i<=N; i++) {
        dist[i] = inf;
        inqueue[i] = false;

        height[i] = 1;
        father[i] = i;
        cup[i] = 0;
    }

    for(int i=1; i<=K; i++) {
        int termita;
        f1 >> termita;

        dist[termita] = 0;
        if(!inqueue[termita]) {
            inqueue[termita] = true;
            q.push(termita);
        }
    }

    for(int i=1; i<=M; i++) {
        int x, y, c;

        f1 >> x >> y >> c;

        G[x].push_back( make_pair(y, c) );
        G[y].push_back( make_pair(x, c) );
    }

    bellmanford();

    computetimes();


    computedisjointset();

    for(int i=1; i<=N; i++) {
        // cout << i << ": " << dist[i] << endl;
    }

    for(int i=0; i<times.size(); i++) {
        // cout << times[i].second.first << ' ' << times[i].second.second << ": " << times[i].first << endl;
    }

    for(int i=1; i<=Q; i++) {
        int x, y, t;

        f1 >> x >> y >> t;

        int ans = query(x, y);

        if(ans > t) {
            f2 << ans - t << '\n';
        }
        else {
            f2 << 0 << '\n';
        }
    }
 
    f1.close();
    f2.close();

    return 0;
}