Cod sursa(job #475593)
#include<fstream>
#include<algorithm>
using namespace std;
const char iname[]="radiatie.in";
const char oname[]="radiatie.out";
const int maxn=15007;
ifstream f(iname);
ofstream g(oname);
struct muchie
{
int a,b,c;
}a[maxn*2];
int height[maxn],A[maxn],cost[maxn],n,m,k,i;
bool operator<(const muchie& a,const muchie& b)
{
return a.c<b.c;
}
int anc(int x)
{
int y;
for(y=x;A[y]!=y;y=A[y]);
return y;
}
void get_height(int x)
{
if(A[x]==x)
{
height[x]=1;
return;
}
if(height[A[x]]==0)
get_height(A[x]);
height[x]=height[A[x]]+1;
}
int query(int x,int y)
{
int rez=0;
while(height[x]>height[y])
rez=max(rez,cost[x]),x=A[x];
while(height[y]>height[x])
rez=max(rez,cost[y]),y=A[y];
while(x!=y)
rez=max(rez,cost[x]),rez=max(rez,cost[y]),x=A[x],y=A[y];
return rez;
}
int main()
{
f>>n>>m>>k;
for(i=1;i<=m;++i)
f>>a[i].a>>a[i].b>>a[i].c;
sort(a+1,a+m+1);
for(i=1;i<=n;++i)
A[i]=i;
for(i=1;i<=m;++i)
{
int x=anc(a[i].a),y=anc(a[i].b);
if(x!=y)
A[x]=y,cost[x]=a[i].c;
}
for(i=1;i<=n;++i)
if(!height[i])
get_height(i);
for(i=1;i<=k;++i)
{
int x,y;
f>>x>>y;
g<<query(x,y)<<"\n";
}
}