记录编号	31395	评测结果	AAAAAAAAAA
题目名称	186.[USACO Oct08] 牧场旅行	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.071 s
提交时间	2011-11-02 15:32:56	内存使用	7.90 MiB

#include <cstdio>
using namespace std;

int way[1001]={0},map[1001][1000]={{0}},dis[1001][1000]={{0}};

void bfs(int st,int en)
{
	int i,que[1000]={0},len[1000]={0},tail=0,head=0;
	bool used[1001]={false};
	que[0]=st;
	len[0]=0;
	used[st]=true;
	while (tail<=head)
	{
		for (i=0;i<way[que[tail]];i++)
			if (!used[map[que[tail]][i]])
			{
				head++;
				que[head]=map[que[tail]][i];
				len[head]=len[tail]+dis[que[tail]][i];
				used[que[head]]=true;
				if (que[head]==en)
				{
					printf("%d\n",len[head]);
					return;
				}
			}
		tail++;
	}
}

int main(void)
{
	freopen("pwalk.in","r",stdin);
	freopen("pwalk.out","w",stdout);
	int i,n,q,temp,temp2,temp3;
	scanf("%d %d\n",&n,&q);
	for (i=1;i<n;i++)
	{
		scanf("%d %d %d\n",&temp,&temp2,&temp3);
		map[temp][way[temp]]=temp2;
		map[temp2][way[temp2]]=temp;
		dis[temp][way[temp]]=temp3;
		dis[temp2][way[temp2]]=temp3;
		way[temp]++;
		way[temp2]++;
	}
	for (i=1;i<=q;i++)
	{
		scanf("%d %d\n",&temp,&temp2);
		bfs(temp,temp2);
	}
	fclose(stdin);
	fclose(stdout);
	return(0);
}