# 11108: 【原1108】二哥的爬树

### 题目描述

author: Qiming Chen 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1108

## Output Format

m行,是这m次询问得到的他们之间的距离.

## Sample Input

``````3
2 1 4
3 1 5
3
1 2
1 3
2 3
``````

## Sample Output

``````4
5
9
``````

## WashSwang's solution

``````#include <iostream>
using namespace std;
int x,y,v,n,m,dis[101][101];
int main() {
cin>>n;
for (int i=0;i<n;++i)
for (int j=0;j<n;++j)
dis[i][j]=0x3f3f3f3f;
for (int i=0;i<n-1;++i){
cin>>x>>y>>v;
dis[x-1][y-1]=v;
dis[y-1][x-1]=v;
dis[i][i]=0;
}
for (int k=0;k<n;++k)
for (int i=0;i<n;++i)
for (int j=0;j<n;++j)
if (dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j]=dis[i][k]+dis[k][j];
cin>>m;
for (int i=0;i<m;++i){
cin>>x>>y;
cout<<dis[x-1][y-1]<<endl;
}
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int const MAX_N = 110;
int main() {

ios::sync_with_stdio(false);
int n, m;
cin >> n;
queue<int> next[MAX_N], cost[MAX_N];
for (int i = 1; i < n; ++i) {
int tmpx, tmpy, c;
cin >> tmpx >> tmpy >> c;
next[tmpx].push(tmpy); cost[tmpx].push(c);
next[tmpy].push(tmpx); cost[tmpy].push(c);
}
cin >> m;
while (m--) {
int start, des, now, tmpcos;
bool found = false, visited[MAX_N];
memset(visited, false, sizeof(visited));
cin >> start >> des;
visited[start] = true;
queue<int> que, cos, tmpnext, tmpcost;
que.push(start);
cos.push(0);
while (true) {
now = que.front();
tmpcos = cos.front();
que.pop(); cos.pop();
tmpnext = next[now]; tmpcost = cost[now];
while (!tmpnext.empty()) {
int nextnode = tmpnext.front(), nextcost = tmpcos + tmpcost.front();
tmpnext.pop(); tmpcost.pop();
if (nextnode == des) {
found = true;
cout << nextcost << endl;
break;
}
if (!visited[nextnode]) {
que.push(nextnode); cos.push(nextcost);
visited[nextnode] = true;
}
}
if (found) break;
}
}
return 0;
}
``````