记录编号	203273	评测结果	AAAAAAAAAA
题目名称	[ZLXOI 2015][异次元圣战III]ZLX的陨落	最终得分	100
用户昵称	高哥	是否通过	通过
代码语言	C++	运行时间	1.049 s
提交时间	2015-11-02 20:51:16	内存使用	2.89 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define N 100010
using namespace std;
int n,m,q,f[N],ans[N],dist[N];
int vis[N],r;
struct Edge{
	int from,to,dist;
};
struct que{
	int from,to;
};
//vector<Edge> edges;
vector<Edge> edge;
vector<que> ques;
vector<int> g[N];
vector<int> Q[N];
int find(int x)
{
	if(x!=f[x])
	 f[x]=find(f[x]);
	return f[x];
}
void add(int u,int v,int w)
{
	edge.push_back((Edge){u,v,w});
	int m=edge.size();
	g[u].push_back(m-1);
}
void addq(int u,int v)
{
	ques.push_back((que){u,v});
	int m=ques.size();
	Q[u].push_back(m-1);
}
void input()
{
	scanf("%d%d",&n,&m);
	int u,v,w;
	for(int i=1;i<=m;i++)
	{
	  scanf("%d%d%d",&u,&v,&w);
	  r=u;
	  add(u,v,w);
	  add(v,u,w);
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&u,&v);
		addq(u,v);
		addq(v,u);
	}
}
void init()
{
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
	  f[i]=i;
}
void tarjan(int x,int fa)
{
	//cout<<dist[x]<<endl;
	vis[x]=1;
	for(int i=0;i<g[x].size();i++)
	{
		Edge u=edge[g[x][i]];
		if(vis[u.to]==0)
		{
		  dist[u.to]=dist[x]+u.dist;
		  tarjan(u.to,x);
		}
	}
	
	for(int i=0;i<Q[x].size();i++)
	{
		int m=Q[x][i];
		m/=2;
		que u=ques[Q[x][i]];
		if(vis[u.to]==2) 
		{
		  // cout<<u.to<<':'<<dist[u.to]<<' '<<x<<':'<<dist[x]<<' '<<find(u.to)<<':'<<dist[find(u.to)]<<endl;
		   ans[m]=dist[u.to]+dist[x]-2*dist[find(u.to)];
		   //cout<<ans[m]<<endl;
		}
	}
	f[x]=fa;
	vis[x]=2;
}
int main()
{
	freopen("ThefallingofZLX.in","r",stdin);
	freopen("ThefallingofZLX.out","w",stdout);
	input();
	init();
	//sort(edges.begin(),edges.end());
	//kruskal();
	tarjan(r,r);
	//cout<<q<<endl;
	for(int i=0;i<q;i++)
	  printf("%d\n",ans[i]);
	return 0;
}