Skip to content

11108: 【原1108】二哥的爬树

题目

题目描述

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

Description

二哥的室友赌博经常输给二哥,被激怒了.

他追打着二哥,把二哥追上了一棵树(树由节点和节点之间的边构成,没有环,但是是全连通的),两个人在树的某两个节点的位置.你要帮二哥计算他们之间隔了多远的距离(沿着树的边计算距离).

有一只小鸟说不会的话可以用邻接矩阵存储...

Input Format

第一行是一个整数n, 表示树一共有n个节点, 他们的编号是1~n. 之后的n-1行,每行有三个数a_i,b_i和c_i中间各用一个空格隔开. a_i, b_i表示树有一条从a_i号节点到b_i号节点的边,c_i是这条边的长度. 再一行是一个整数m, 表示有m次询问. 之后m行每行有两个数d_j和e_j,中间用一个空格隔开,表示二哥和室友在这两个节点的位置上,请你帮助计算他们的距离.

Output Format

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

Restrictions

对于100%的数据n<=100.

对于100%的数据m<=10.

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;
}