记录编号	299034	评测结果	AAAAAAAAAA
题目名称	1439.[NOIP 2013]货车运输	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.046 s
提交时间	2016-08-23 17:09:46	内存使用	0.69 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
namespace mine{
	inline int getint(){
		static int __c,__x;
		static bool __neg;
		__x=0;
		__neg=false;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		if(__c=='-'){
			__neg=true;
			__c=getchar();
		}
		for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10+(__c^48);
		if(__neg)return -__x;
		return __x;
	}
	inline void putint(int __x){
		static int __a[40],__i,__j;
		static bool __neg;
		__neg=__x<0;
		if(__neg)__x=-__x;
		__i=0;
		do{
			__a[__i++]=__x%10+48;
			__x/=10;
		}while(__x);
		if(__neg)putchar('-');
		for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
	}
}
using namespace mine;
const int maxn=10010,maxe=50010;
struct edge1{
	int from,to,dis;
	bool operator<(const edge1 &x)const{
		return dis>x.dis;
	}
}ee[maxe];
struct edge{
	int to,dis,prev;
}e[maxn<<2];
void insert(int,int,int);
void Kruskal();
int findroot(int);
void mergeset(int,int);
void dfs1(int);
void dfs2(int,int);
void RMQ_init();
int log2(int);
int RMQ_min(int,int);
int query(int,int);
int anc[maxn],prt[maxn]={0},w[maxn],mn[maxn][15],last[maxn]={0},len=0;
int top[maxn],size[maxn],soni[maxn]={0},son[maxn]={0},depth[maxn],first[maxn],tim=0,id[maxn];
int n,m,q,x,y;
inline int MAIN(){
#define MINE
#ifdef MINE
	freopen("truck.in","r",stdin);
	freopen("truck.out","w",stdout);
#endif
	n=getint();
	m=getint();
	for(int i=1;i<=m;i++){
		ee[i].from=getint();
		ee[i].to=getint();
		ee[i].dis=getint();
	}
	Kruskal();
	depth[1]=1;
	dfs1(1);
	dfs2(1,1);
	RMQ_init();
	q=getint();
	while(q--){
		x=getint();
		y=getint();
		putint(query(x,y));
		putchar('\n');
	}
	return 0;
}
inline void insert(int x,int y,int z){
	e[++len].to=y;
	e[len].dis=z;
	e[len].prev=last[x];
	last[x]=len;
}
inline void Kruskal(){
	int x,y,cnt=1;
	sort(ee+1,ee+m+1);
	for(int i=1;i<=n;i++)anc[i]=i;
	for(int i=1;cnt<n&&i<=m;i++){
		x=ee[i].from;
		y=ee[i].to;
		if(findroot(x)==findroot(y))continue;
		cnt++;
		mergeset(x,y);
		insert(x,y,ee[i].dis);
		insert(y,x,ee[i].dis);
	}
	for(int i=2;cnt<n&&i<=n;i++)if(findroot(i)!=findroot(1)){
		cnt++;
		mergeset(1,i);
		insert(1,i,-1);
		insert(i,1,-1);
	}
}
inline int findroot(int x){
	int rt;
	for(rt=anc[x];anc[rt]!=rt;rt=anc[rt]);
	for(;anc[x]!=x;x=anc[x])anc[x]=rt;
	return rt;
}
inline void mergeset(int x,int y){
	int rx=findroot(x),ry=findroot(y);
	if(rx==ry)return;
	anc[rx]=ry;
}
inline void dfs1(int x){
	int y;
	size[x]=1;
	for(int i=last[x];i;i=e[i].prev){
		y=e[i].to;
		if(y==prt[x])continue;
		prt[y]=x;
		depth[y]=depth[x]+1;
		dfs1(y);
		size[x]+=size[y];
		if(size[y]>size[son[x]]){
			son[x]=y;
			soni[x]=i;
		}
	}
}
inline void dfs2(int x,int tp){
	int y;
	first[x]=++tim;
	id[tim]=x;
	top[x]=tp;
	if(son[x]){
		w[son[x]]=e[soni[x]].dis;
		dfs2(son[x],tp);
	}
	for(int i=last[x];i;i=e[i].prev){
		y=e[i].to;
		if(y==prt[x]||y==son[x])continue;
		w[y]=e[i].dis;
		dfs2(y,y);
	}
}
inline void RMQ_init(){
	for(int i=1;i<=n;i++)mn[i][0]=w[id[i]];
	for(int j=1;(1<<j)<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++)
		mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
}
inline int log2(int x){
	int i=-1;
	for(;x;x>>=1)i++;
	return i;
}
inline int RMQ_min(int l,int r){
	int k=log2(r-l+1);
	return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
inline int query(int x,int y){
	int fx=top[x],fy=top[y],ans=~(1<<31);
	while(fx!=fy){
		if(depth[fx]<depth[fy]){
			swap(fx,fy);
			swap(x,y);
		}
		ans=min(ans,RMQ_min(first[fx],first[x]));
		x=prt[fx];
		fx=top[x];
	}
	if(depth[x]>depth[y])swap(x,y);
	if(x!=y)ans=min(ans,RMQ_min(first[x]+1,first[y]));
	return ans;
}
int hzoier=MAIN();
int main(){;}
/*
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
*/