Eva

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 3689  Solved: 1801
Description

给你N个点的无向图 (1 <= N <= 15,000)，记为：1…N。 
图中有M条边 (1 <= M <= 30,000) ，第j条边的长度为： d_j ( 1 < = d_j < = 1,000,000,000).

现在有 K个询问 (1 < = K < = 20,000)。 
每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少？

Input

第一行： N, M, K。 
第2..M+1行: 三个正整数：X, Y, and D (1 <= X <=N; 1 <= Y <= N). 表示X与Y之间有一条长度为D的边。 
第M+2..M+K+1行: 每行两个整数A B,表示询问从A点走到B点的所有路径中，最长的边最小值是多少？

Output

 对每个询问，输出最长的边最小值是多少。

Sample Input

6 6 8
1 2 5
2 3 4
3 4 3
1 4 8
2 5 7
4 6 2
1 2
1 3
1 4
2 3
2 4
5 1
6 2
6 1

Sample Output

5
5
5
4
4
7
4
5

HINT

1 <= N <= 15,000

1 <= M <= 30,000

1 <= d_j <= 1,000,000,000

1 <= K <= 15,000

/**************************************************************

    Problem: 3732

    User: ictsing

    Language: C++

    Result: Accepted

    Time:308 ms

    Memory:6420 kb

****************************************************************/

 

//BZOJ3732 Network

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

struct node

{

    int x,y,w;

}e[30000+5];

const int mt = 15000+5;

const int inf = 1e9;

int nxt[mt<<1],to[mt<<1],w[mt<<1],adj[mt<<1],f[mt<<1];

int g[mt<<1],fa[mt][20],dis[mt<<1],ans[mt<<1][20],dep[mt<<1];

int ecnt=0;

int n,m,T_T;

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

bool cmp(node a,node b)

{

    return a.w<b.w;

}

int findf(int x)

{

    if(f[x]==x) return x;

    return f[x]=findf(f[x]);

}

void adde(int u,int v,int ww)

{

    ecnt++,to[ecnt]=v,w[ecnt]=ww,nxt[ecnt]=adj[u],adj[u]=ecnt;

    ecnt++,to[ecnt]=u,w[ecnt]=ww,nxt[ecnt]=adj[v],adj[v]=ecnt;

}

void dfs(int x)

{

    for(int i=adj[x];i;i=nxt[i])

    {

        int v=to[i];

        if(v!=g[x])

        {

            g[v]=x;

            dis[v]=w[i];

            dep[v]=dep[x]+1;

            dfs(v);

        }

    }

}

int lca(int x,int y)

{

    int res=0;

    if(dep[x]<dep[y]) swap(x,y);

    for(int i=19;i>=0;i--) 

        if((dep[x]-dep[y])&(1<<i)) res=max(res,ans[x][i]),x=fa[x][i];

    if(x==y) return res;

    for(int i=19;i>=0;i--)

        if(fa[x][i]!=fa[y][i])

        {

            res=max(res,max(ans[x][i],ans[y][i]));

            x=fa[x][i],y=fa[y][i];

        }

    return max(res,max(dis[x],dis[y]));

}

int main()

{

    n=read(),m=read(),T_T=read();

    for(int i=1;i<=m;i++)

    {

        e[i].x=read(),e[i].y=read(),e[i].w=read();

    }

    sort(e+1,e+m+1,cmp);

    for(int i=1;i<=n;i++) f[i]=i;

    for(int i=1;i<=m;i++)

    {

        int a=findf(e[i].x);

        int b=findf(e[i].y);

        if(a!=b)

        {

            f[a]=b;

            adde(e[i].x,e[i].y,e[i].w);

        }

    }

    g[1]=0,dis[1]=0;

    dfs(1);

    for(int i=1;i<=n;i++) fa[i][0]=g[i];

    for(int j=1;j<=19;j++)

        for(int i=1;i<=n;i++)

            if(fa[i][j-1]) fa[i][j]=fa[fa[i][j-1]][j-1];

            else fa[i][j]=0;

    for(int i=1;i<=n;i++) ans[i][0]=dis[i];

    for(int j=1;j<=19;j++)

        for(int i=1;i<=n;i++)

            if(fa[i][j-1]) ans[i][j]=max(ans[i][j-1],ans[fa[i][j-1]][j-1]);

    while(T_T--)

    {

        int x=read(),y=read();

        printf("%d\n",lca(x,y));

    }

    return 0;

}