Cod sursă (job #144267)

// Andrei Parvu

// Timpul este un cerc plat: ori de cate ori vom rula acest program, nodurile
// tot in acelasi moment de timp se vor desparti

#include <cstdio>
#include <cstring>

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int NMAX = 300000;

// p-asta il faci 2 daca vrei sa fiecare termita sa plece la un anumit moment
// de timp (nu neaparat la 0)
#define TYPE 1

#define START 0

int father[NMAX + 1], edge_cost[NMAX + 1], h[NMAX + 1];
vector<pair<int, int> > v[NMAX + 1];

int cost[NMAX + 1];
vector<pair<int, int> > dists;

bool in_queue[NMAX + 1];
int part_cost[NMAX + 1], have_been[NMAX + 1];

int link_up(int x) {
  for (; father[x]; x = father[x]);

  return x;
}

void unite(int x, int y, int cost) {
  x = link_up(x);
  y = link_up(y);

  if (x == y) {
    return ;
  }

  if (h[x] < h[y]) {
    father[x] = y;
    edge_cost[x] = cost;
  } else {
    if (h[x] == h[y]) {
      h[x]++;
    }
    father[y] = x;
    edge_cost[y] = cost;
  }
}

int main() {
  freopen("termite.in", "rt", stdin);
  freopen("termite.out", "wt", stdout);

  int n, m, k, q;

  scanf("%d%d%d%d", &n, &m, &k, &q);
  for (int i = 0; i < k; i++) {
    int x, cost = 0;

    scanf("%d", &x);
#if (TYPE == 2)
      scanf("%d", &cost);
#endif

    v[START].push_back(make_pair(x, cost));
    v[x].push_back(make_pair(START, cost));
  }
  for (int i = 0; i < m; i++) {
    int x, y, cost;

    scanf("%d%d%d", &x, &y, &cost);

    v[x].push_back(make_pair(y, cost));
    v[y].push_back(make_pair(x, cost));
  }

  memset(cost, 0x3f, sizeof(cost));
  cost[START] = 0;
  in_queue[START] = false;
  queue<int> queue;
  queue.push(START);

  while (!queue.empty()) {
    int x = queue.front();
    queue.pop();
    in_queue[x] = false;

    for (unsigned int i = 0; i < v[x].size(); i++) {
      int next = v[x][i].first;

      if (cost[x] + v[x][i].second < cost[next]) {
        cost[next] = cost[x] + v[x][i].second;

        if (!in_queue[next]) {
          in_queue[next] = true;
          queue.push(next);
        }
      }
    }
  }

  for (int i = 1; i <= n; i++) {
    dists.push_back(make_pair(cost[i], i));
  }

  sort(dists.begin(), dists.end());

  for (int i = n - 1; i >= 0; i--) {
    int x = dists[i].second;

    for (unsigned int j = 0; j < v[x].size(); j++) {
      int next = v[x][j].first;

      if (cost[next] >= dists[i].first) {
        unite(x, next, dists[i].first);
      }
    }
  }

  for (int i = 1; i <= q; i++) {
    int x, y, time;

    scanf("%d%d%d", &x, &y, &time);

    int cur_cost = 0;
    if (x == y) {
      cur_cost = cost[x];
    } else {
      part_cost[x] = 0x3f3f3f3f;
      for (; x; x = father[x]) {
        have_been[x] = i;
        part_cost[father[x]] = edge_cost[x];
      }
      for (; y; y = father[y]) {
        if (have_been[y] == i) {
          cur_cost = part_cost[y];
          break;
        }
        part_cost[father[y]] = min(part_cost[father[y]], edge_cost[y]);
      }
    }

    if (cur_cost < time) {
      printf("%d\n", 0);
    } else {
      printf("%d\n", cur_cost - time);
    }
  }

  return 0;
}