记录编号	228660	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 牧场旅行	最终得分	100
用户昵称	SOBER GOOD BOY	是否通过	通过
代码语言	C++	运行时间	0.603 s
提交时间	2016-02-19 14:27:50	内存使用	9.60 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=1010;
int dis[maxn]={0};
int head[maxn],n,m,q,k,ji[maxn],len=0;
struct Edge
{
	int dis,to,next;
}e[maxn*maxn];
struct Node
{
	int num,dis;
	Node(){};
	Node(int x,int y)
	{
		num=x,dis=y;
	};
	bool operator <(const Node &a)const
	{
		return dis>a.dis;
	}
};
void Init();
void Insert(int,int,int);
void Dijs(int,int );
int main()
{
	freopen("pwalk.in","r",stdin);
	freopen("pwalk.out","w",stdout);
	Init();
	for(int i=1;i<=q;i++)
	{
		int x,y;
		cin>>x>>y;
		Dijs(x,y);
	}
	return 0;
}
void Init()
{
	memset(e,0,sizeof(e));
	memset(head,-1,sizeof(head));
	memset(ji,0,sizeof(ji));
	cin>>n>>q;
	int l=n-1;
	for(int i=1;i<=l;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		Insert(x,y,z);
		Insert(y,x,z);
	}
}
void Insert(int x,int y,int z )
{
	len++;
	e[len].to=y;
	e[len].dis=z;
	e[len].next=head[x];
	head[x]=len;
}
void Dijs(int x,int y)
{
	bool f[maxn]={0};
	int d[maxn];
	memset(d,0x7f,sizeof(d));
	priority_queue<Node> q;
	d[x]=0;
	f[x]=1;
	q.push(Node(x,d[x]));
	while(!q.empty())
	{
		Node ding=q.top();q.pop();
		int k=ding.num;f[k]=1;
		for(int i=head[k];i!=-1;i=e[i].next)
		{
			int h=e[i].to;
			if(d[h]>d[k]+e[i].dis)
			{
				d[h]=d[k]+e[i].dis;
				q.push(Node(h,d[h]));
			}
		}
	}
	cout<<d[y]<<endl;
}