Cod sursa(job #460959)

Utilizator S7012MYPetru Trimbitas S7012MY Data 4 iunie 2010 20:38:46
Problema Radiatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#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;
}