Cod sursa(job #460959)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define DM 30001
int x[DM],y[DM],c[DM],cost[15001],gr[15001],ind[DM],inaltime[15001],n,m,k;
bool cmp(int i,int j) { return c[i]<c[j];}
int gaseste(int i) {
int j;
for(j=i; j!=gr[j]; j=gr[j]);
return j;
}
void dfs(int x) {
if(x==gr[x]) inaltime[x]=1;
else {
dfs(gr[x]);
inaltime[x]=inaltime[gr[x]]+1;
}
}
int main()
{
int i,a,b,q1,q2,sol;
freopen("radiatie.in","r",stdin);
freopen("radiatie.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
for (i=1;i<=m;i++ ) {
scanf("%d %d %d",&x[i],&y[i],&c[i]);
ind[i]=i;
if(i<=n) gr[i]=i;
}
sort(ind+1,ind+m+1,cmp);
for (i=1; i<=m;i++) {
a=gaseste(x[ind[i]]);
b=gaseste(y[ind[i]]);
if(a!=b) {
gr[a]=b;
cost[a]=c[ind[i]];
}
}
for(i=1;i<=n;i++)
if(!inaltime[i])
dfs(i);
for (i=1; i<=k;++i) {
scanf("%d %d",&q1,&q2);
sol=0;
for( ;inaltime[q1] > inaltime[q2];q1=gr[q1])
sol=max(sol,cost[q1]);
for( ;inaltime[q1] < inaltime[q2];q2=gr[q2] )
sol=max(sol,cost[q2]);
for( ;q1!=q2; q1=gr[q1],q2=gr[q2] ){
sol=max(sol,cost[q1]);
sol=max(sol,cost[q2]);
}
printf("%d\n",sol);
}
return 0;
}