- 货车运输
 - @ 2015-09-25 18:16:55
 
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
long long n,m,q,i,j,k,cnt=0,dis[10001];
bool vis[10001];
struct edge{
    long long l,r,v;
}e[50001];
bool comp(const edge &a,const edge &b){return a.v>b.v;}
struct node{
    long long unipa,pa,s;
    long long dis;
}p[10001];
void init(){
    for(i=1;i<=n;++i){
        p[i].pa=p[i].unipa=i;
        p[i].s=1;
    }
}
long findset(long long x){
    long long tmp1,tmp2=x;
    while(x!=p[x].unipa)x=p[x].unipa;
    while(tmp2!=p[tmp2].unipa){
        tmp1=p[tmp2].unipa;
        p[tmp2].unipa=x;
        tmp2=tmp1;
    }
    return x;
}
void uni(long long a,long long b,long long len){
    long long tmp1=findset(a),tmp2=findset(b);
    if(tmp1==tmp2)return;
    if(p[tmp1].s<p[tmp2].s){
        p[tmp1].pa=tmp2;
        p[tmp1].unipa=tmp2;
        p[tmp2].s+=p[tmp1].s;
        p[tmp1].dis=len;
    }
    else{
        p[tmp2].pa=tmp1;
        p[tmp2].unipa=tmp1;
        p[tmp1].s+=p[tmp2].s;
        p[tmp2].dis=len;
    }
}
bool check(long long a,long long b){
    long long tmp1=findset(a),tmp2=findset(b);
    return tmp1==tmp2;
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(i=1;i<=m;++i)scanf("%lld%lld%lld",&e[i].l,&e[i].r,&e[i].v);
    init();
    sort(e+1,e+m,comp);
    for(i=1;i<=m&&cnt!=n-1;++i)
        if(!check(e[i].l,e[i].r)){
            ++cnt;
            uni(e[i].l,e[i].r,e[i].v);
        }
    scanf("%lld",&q);
    for(i=1;i<=q;++i){
        memset(vis,0,sizeof(vis));
        memset(dis,0x3f,sizeof(dis));
        long long tmp1,tmp2;
        scanf("%lld%lld",&tmp1,&tmp2);
        if(check(tmp1,tmp2)){
            long long tmp3=tmp1,mn=100000000;
            vis[tmp1]=1;
            while(p[tmp3].pa!=tmp3){
                vis[tmp3]=1;
                dis[p[tmp3].pa]=min(dis[tmp3],p[tmp3].dis);
                tmp3=p[tmp3].pa;
            }
            vis[tmp3]=1;
            while(!vis[tmp2]){
                mn=min(mn,p[tmp2].dis);
                tmp2=p[tmp2].pa;
            }
            printf("%lld\n",min(mn,dis[tmp2]));
        }
        else printf("-1\n");
    }
}
有人有那个点的数据吗?
0 条评论
信息
- ID
 - 1843
 - 难度
 - 7
 - 分类
 - (无)
 - 标签
 - 递交数
 - 5320
 - 已通过
 - 955
 - 通过率
 - 18%
 - 被复制
 - 10
 - 上传者