Caminhão_SBC_2013.cpp

#include <bits/stdc++.h>

using namespace std;

#define MAX_JUMP 15

struct Node {
  int level;
  vector< pair<int, int> > neigh;
};

Node graph[20000];

struct Edge {
  int a, b, p;
};

Edge edge[100000];

bool compare_edge(Edge x, Edge y) {
  if (x.p > y.p) {
    return true;
  }
  
  return false;
}

int parent[20000];

int find_pat(int x) {
  if (parent[x] == x) {
    return x;
  }
  
  parent[x] = find_pat(parent[x]);
  return parent[x];
}

void join(int a, int b) {
  int pat_a = find_pat(a);
  int pat_b = find_pat(b);
  
  parent[pat_a] = pat_b;
}

void kruskal(int n, int m) {
  for (int i = 0; i < n; i++) {
  	graph[i].neigh.clear();
  }
  //cout << "Limpou o grafo do kruskal" << endl;
  
  sort(edge, edge + m, compare_edge);
  //cout << "Ordenou as arestas" << endl;
  
  for (int i = 0; i < n; i++) {
    parent[i] = i;
  }
  
  for (int i = 0; i < m; i++) {
    int a = edge[i].a, b = edge[i].b, p = edge[i].p;
    
    if (find_pat(a) != find_pat(b)) {
      join(a, b);
      
      graph[a].neigh.push_back(make_pair(b, p));
      graph[b].neigh.push_back(make_pair(a, p));
    }
  }
}

pair<int, int> p[20000][MAX_JUMP];

void dfs(int act) {
  if (act == 0) {
    graph[0].level = 0;
  }
  
  for (int i = 0; i < graph[act].neigh.size(); i++) {
    int son = graph[act].neigh[i].first;
    
    if (son != p[act][0].first) {
      p[son][0] = make_pair(act, graph[act].neigh[i].second);
      graph[son].level = graph[act].level + 1;
      
      dfs(son);
    }
  }
}

int LCA(int a, int b, int minn) {
  int diff = abs(graph[a].level - graph[b].level);
  
  if (diff == 0) {
    if (a == b) {
      return minn;
    }
    
    for (int k = MAX_JUMP - 1; k >= 0; k--) {
      if (p[a][k].first != -1 && p[a][k].first != p[b][k].first) {
      	minn = min(minn, min(p[a][k].second, p[b][k].second));
      	
        a = p[a][k].first;
        b = p[b][k].first;
      }
    }
    
    return min(minn, min(p[a][0].second, p[b][0].second));
  } else {
    int jump = log2(diff);
    
    if (graph[a].level < graph[b].level) {
      return LCA(a, p[b][jump].first, min(minn, p[b][jump].second));
    } else {
      return LCA(p[a][jump].first, b, min(minn, p[a][jump].second));
    }
  }
}

int main() {
  int n, m, q;
  while (scanf("%d%d%d", &n, &m, &q) != EOF) {
    for (int i = 0; i < m; i++) {
      scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].p);
      edge[i].a--;
      edge[i].b--;
    }
    
    for (int i = 0; i < n; i++) {
    	for (int j = 0; j < MAX_JUMP; j++) {
    		p[i][j].first = -1;
    		p[i][j].second = -1;
		}
	}
    
    //cout << "Conseguiu preencher as arestas!" << endl;
    
    kruskal(n, m); // Uma pérola!
    
    //cout << "Conseguiu rodar o kruskal!" << endl;
    
    dfs(0); // Caramba funcionou!
    
    for (int k = 1; k < MAX_JUMP; k++) {
      for (int j = 1; j < n; j++) {
        if (p[j][k - 1].first != -1) {
          p[j][k] = make_pair(p[p[j][k - 1].first][k - 1].first, min(p[j][k - 1].second, p[p[j][k - 1].first][k - 1].second));
        }
      }
    }
    
    //cout << "Chegou nas queryes!" << endl;
    for (int i = 0; i < q; i++) {
      int a, b;
      scanf("%d%d", &a, &b);
      printf("%d\n", a != b ? LCA(--a, --b, 100001) : -1);
    }
    //cout << "Saiu das queryes!" << endl;
  }
}