记录编号	252200	评测结果	AAAAAAAAAA
题目名称	图的询问	最终得分	100
用户昵称	asddddd	是否通过	通过
代码语言	C++	运行时间	1.721 s
提交时间	2016-04-19 19:37:53	内存使用	3.09 MiB

    //
    // main.cpp
    // tudexunwen
    //
    // Created by Qing Liu on 16/4/19.
    // Copyright 漏 2016骞 Qing Liu. All rights reserved.
    //
     
    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    #include <vector>
    #define maxn 55005
    using namespace std;
    struct edge{
    int from,to,cost;
    };
    struct edg{
    int to,cost;
    };
    vector<edg>G[maxn];
    int pa[maxn],val[maxn];
    int _find(int a){
    if(pa[a]==a){
    return a;
    }
    else return _find(pa[a]);
    }
    edge haha[30005];
    bool cmp1(const edge &a ,const edge &b){
    return a.cost<b.cost;
    }
    struct fuck{
    int to,id;
    };
    struct hah{
    int a,b;
    };
    hah que[maxn];
    vector<fuck>ask_[maxn];
    int ans[maxn],_ansestor[maxn],par[maxn];
    bool vis[maxn];
    void tarjan(int x,int paa){
    for(int i=0;i<G[x].size();i++){
    const edg &e=G[x][i];
    if(e.to!=paa){
    par[e.to]=x;
    val[e.to]=e.cost;
    tarjan(e.to,x);
    int ppa=_find(e.to),ppb=_find(x);
    pa[ppa]=ppb;
    _ansestor[_find(x)]=x;
    }
    }
    vis[x]=1;
    for (int i=0; i<ask_[x].size(); i++) {
    fuck &ZLX=ask_[x][i];
    if(vis[ZLX.to]){
    if(ans[ZLX.id])
    continue;
    ans[ZLX.id]=_ansestor[_find(ZLX.to)];
    }
    }
    }
    void init(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
    pa[i]=i;
    edge &a=haha[i];
    cin>>a.from>>a.to>>a.cost;
    }
    sort(haha+1, haha+m+1, cmp1);
    for(int i=1;i<=m;i++){
    int from=haha[i].from,to=haha[i].to;
    int ppa=_find(from),ppb=_find(to);
    if(ppa!=ppb){
    pa[ppa]=pa[ppb];
    //cout<<from<<" "<<to<<endl;
    G[from].push_back((edg){to,haha[i].cost});
    G[to].push_back((edg){from,haha[i].cost});
    }
    }
    for (int i=1; i<=k; i++) {
    int from,to;
    cin>>from>>to;
    que[i].a=from,que[i].b=to;
    ask_[from].push_back((fuck){to,i});
    ask_[to].push_back((fuck){from,i});
    }
    for (int i=1; i<=n; i++) {
    pa[i]=i;
    _ansestor[i]=i;
    }
    tarjan(1,1);
    for (int i=1;i<=k;i++) {
    int k=ans[i];
    int anss=-999999999;
    int l=que[i].a;
    int r=que[i].b;
    while(l!=k){
    anss=max(anss, val[l]);
    l=par[l];
    }
    while (r!=k) {
    anss=max(anss, val[r]);
    r=par[r];
    }
    ans[i]=anss;
    }
    for (int i=1; i<=k; i++) {
    cout<<ans[i]<<endl;
    }
    }
    int main(int argc, const char * argv[]) {
    freopen("heatwave.in", "r", stdin);
    freopen("heatwave.out", "w", stdout);
    init();
    return 0;
    }