记录编号	325857	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 牧场旅行	最终得分	100
用户昵称	NVIDIA	是否通过	通过
代码语言	C++	运行时间	0.276 s
提交时间	2016-10-20 17:01:51	内存使用	3.76 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
const int maxn=0x7ffff;
int n,m,x,y,z,r;
int dis[1005][1005],vis[1005];
struct Edge{
	int from,to,dist;
	Edge(int u,int v,int d):from(u),to(v),dist(d){}
};
using namespace std;
vector<Edge>edges;
vector<int>G[1005];
queue<int> q;
inline void add(int u,int v,int d){
	edges.push_back((Edge){u,v,d}) ;
	r=edges.size() ;
	G[u].push_back(r-1);
	edges.push_back((Edge){v,u,d}) ;
	r=edges.size() ;
	G[v].push_back(r-1);
}
inline void spfa(int s){
	memset(vis,0,sizeof(vis));
	
	for(int i=0;i<=n;i++)dis[s][i]=maxn;
	dis[s][s]=0;
	vis[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		vis[u]=0;
		for(int i=0;i<G[u].size();i++){
			Edge& e=edges[G[u][i]];
			if(dis[s][u]<maxn&&dis[s][e.to]>dis[s][u]+e.dist){
				dis[s][e.to]=dis[s][u]+e.dist;
				if(!vis[e.to])
				{
					q.push(e.to);
					vis[e.to]=1;
				}
			}
		}
	}
}
int main()
{ 
	freopen("pwalk.in","r",stdin);
	freopen("pwalk.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n-1;i++){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	for(int i=1;i<=n;i++){
		spfa(i);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		printf("%d",dis[x][y]);
		if(i!=m)printf("\n");
	}
	
	return 0;
}