- 货车运输
- 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
- 分类
- (无)
- 标签
- 递交数
- 5319
- 已通过
- 954
- 通过率
- 18%
- 被复制
- 10
- 上传者