记录编号 220717 评测结果 AAAAAAAAAA
题目名称 [USACO Oct08] 牧场旅行 最终得分 100
用户昵称 Gravatarliu_runda 是否通过 通过
代码语言 C++ 运行时间 0.063 s
提交时间 2016-01-20 10:39:25 内存使用 4.96 MiB
显示代码纯文本
#include<cstdio>
#include<cstring>
using namespace std;
struct edge{
	int to,dis,next;
}lst[3500];
int len=1;
int first[1050];
void insert(int v1,int v2,int d){
	lst[len].to = v2;
	lst[len].next = first[v1];
	lst[len].dis = d;
	first[v1] = len++;
}
int q[1500];
int head,tail;
int ans[1100][1100];
bool vis[1100];
void bfs(int a){
	head = tail = 0;
	memset(q,0,sizeof(q));
	memset(vis,0,sizeof(vis));
	q[tail++] = a;
	ans[a][a]=0;
	vis[a] = true;
	while(head!=tail){
		int v = q[head++];
		for(int pt = first[v];pt;pt = lst[pt].next){
			if(!vis[lst[pt].to]){
				vis[lst[pt].to] = true;
				ans[a][lst[pt].to] = ans[a][v] + lst[pt].dis;
				q[tail++]=lst[pt].to;
			}
		}
	}
}
int main(){
	freopen("pwalk.in","r",stdin);
	freopen("pwalk.out","w",stdout);
	int n,q;
	scanf("%d %d",&n,&q);
	int a,b,c;
	
	for(int i = 1;i<n;++i){
		scanf("%d %d %d",&a,&b,&c);
		insert(a,b,c);
		insert(b,a,c);
	}
	
	for(int i = 1;i<=n;++i)bfs(i);
	
	for(int i = 0;i<q;++i){
		scanf("%d %d",&a,&b);
		printf("%d\n",ans[a][b]);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}