记录编号	4849	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 牧场旅行	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	0.682 s
提交时间	2008-10-22 20:57:33	内存使用	4.09 MiB

/*
ID: cmykrgb1
LANG: C++
TASK: pwalk
*/

#include <iostream>
#define MAX 1001
using namespace std;

class list
{
public:
	list *next;
	int p;
	list(int tp)
	{
		p=tp;
		next=0;
	}
};

class tadjl
{
public:
	list *first,*last;
	void ins(int p)
	{
		if (first)
			last=last->next=new list(p);
		else
			first=last=new list(p);
	}
	tadjl()
	{
		first=last=0;
	}
};

class tQueue
{
public:
	class linklist
	{
	public:
		linklist* next;
		int value;
		linklist()
		{
			next=0;
			value=0;
		}
	};
	linklist *first,*last;
	int size;
	void ins(int p)
	{
		if (size==0)
			first=last=new linklist;
		else
			last=last->next=new linklist;
		last->value=p;
		size++;
	}
	int pop()
	{
		int rtn=first->value;
		linklist *tfirst=first;
		first=first->next;
		delete tfirst;
		size--;
		return rtn;
	}
	void reset()
	{
		size=0;
		first=last=0;
	}
	tQueue()
	{
		reset();
	}
};

tQueue Q;
int N,U;
int dis[MAX][MAX];
bool vis[MAX];
tadjl adjl[MAX];

void init()
{
	int i,a,b,v;
	freopen("pwalk.in","r",stdin);
	freopen("pwalk.out","w",stdout);
	cin >> N >> U;
	for (i=1;i<N;i++)
	{
		scanf("%d%d%d",&a,&b,&v);
		dis[a][b]=dis[b][a]=v;
		adjl[a].ins(b);
		adjl[b].ins(a);
	}
}

void BFS(int s)
{
	int i,j,v;
	list *k;
	Q.reset();
	Q.ins(s);
	memset(vis,0,sizeof(vis));
	vis[s]=true;
	while (Q.size)
	{
		i=Q.pop();
		for (k=adjl[i].first;k;k=k->next)
		{
			j=k->p;
			v=dis[i][j];
			if (!vis[j])
			{
				vis[j]=true;
				dis[s][j]=dis[s][i]+v;
				Q.ins(j);
			}
		}
	}
}

void solve()
{
	int i,a,b;
	for (i=1;i<=N;i++)
	{
		BFS(i);
	}
	for (i=1;i<=U;i++)
	{
		scanf("%d%d",&a,&b);
		printf("%d\n",dis[a][b]);
	}
}

int main()
{
	init();
	solve();
	return 0;
}