记录编号 |
220717 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[USACO Oct08] 牧场旅行 |
最终得分 |
100 |
用户昵称 |
liu_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;
}