记录编号	31867	评测结果	RRRRRRRRRR
题目名称	99.查数	最终得分	0
用户昵称	wangmengyuan	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2011-11-04 11:00:05	内存使用	7.92 MiB

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,w[1001][1001][2];
int a,b,q[1001][2],answer,qi,mo;
bool used[1001]={0};
int ji[1001]={0};
void bfs(int x);
int main()
{
	freopen ("pwalk.in","r",stdin);
	freopen ("pwalk.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=0;i<n-1;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		ji[a]++;
		ji[b]++;
		w[a][ji[a]][0]=b;
		w[a][ji[a]][1]=c;
		w[b][ji[b]][0]=a;
		w[b][ji[b]][1]=c;
	}
	for (int i=0;i<m;i++)
	{
		scanf("%d%d",&a,&b);
		q[0][0]=a;
		q[0][1]=0;
		for (int j=0;j<n-1;j++)
		{
			used[j]=0;
		}
		if (a==b)
		{
			cout<<0<<endl;
			continue;
		}
		qi=0;
		mo=0;
		answer=0;
		while (qi<=mo)
		{
			bfs(qi);
			if (answer==1)
				break;
			qi++;
		}
	}
	return 0;
}
void bfs(int x)
{
	for (int i=1;i<=ji[q[x][0]];i++)
	{
		if (w[q[x][0]][i][0]==b)
		{
			cout<<q[x][1]+w[q[x][0]][i][1]<<endl;
			answer=1;
			return;
		}
		if (used[w[q[x][0]][i][0]])
		{
			continue;
		}
		mo++;
		q[mo][0]=w[q[x][0]][i][0];
		q[mo][1]=q[x][1]+w[q[x][0]][i][1];
		used[q[x][0]]=1;
	}
}