蓝桥 大臣的旅费 (数的直径)

简介: 蓝桥 大臣的旅费 (数的直径)

题目描述
很久以前,T王国空前繁荣。为了更好地管理国家,王国修建了大量的快速路,用于连接首都和王国内的各大城市。
为节省经费,T国的大臣们经过思考,制定了一套优秀的修建方案,使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时,如果不重复经过大城市,从首都到达每个大城市的方案都是唯一的。
J是T国重要大臣,他巡查于各大城市之间,体察民情。所以,从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋,用于存放往来城市间的路费。
聪明的J发现,如果不在某个城市停下来修整,在连续行进过程中,他所花的路费与他已走过的距离有关,在走第x千米到第x+1千米这一千米中(x是整数),他花费的路费是x+10这么多。也就是说走1千米花费11,走2千米要花费23。
J大臣想知道:他从某一个城市出发,中间不休息,到达另一个城市,所有可能花费的路费中最多是多少呢?
输入
输入的第一行包含一个整数n,表示包括首都在内的T王国的城市数
城市从1开始依次编号,1号城市为首都。
接下来n-1行,描述T国的高速路(T国的高速路一定是n-1条)
每行三个整数Pi, Qi, Di,表示城市Pi和城市Qi之间有一条高速路,长度为Di千米。
输出
输出一个整数,表示大臣J最多花费的路费是多少。
样例输入
5
1 2 2
1 3 1
2 4 5
2 5 4
样例输出
135

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int d[100005], v[100005], w[100005];
int first[100005], nextt[100005];
int sum=0, ans=0;
int p;

void add(int x, int y, int z){
   
    sum++;//sum表示边的编号 
    v[sum]=y;
    w[sum]=z;
    nextt[sum]=first[x];
    first[x]=sum;    
}
void dfs(int x, int father){
   
//father表示起点为x的边是从father到x得到的,防止从father到x后又搜索x到father 
    if (ans<d[x]){
   
        ans=d[x];
        p=x;
    } 
    for (int i=first[x]; i!=0; i=nextt[i]){
   
        int j=v[i];
        if (j==father)
            continue;
        d[j]=d[x]+w[i];
        dfs(j, x);
    }
}
void find(int x){
   
    ans=0;
    d[x]=0;
    dfs(x, 0);
}
int main(){
   
    int n;
    scanf("%d", &n);
    for (int i=1; i<=n-1; i++){
   
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);//无向图 
    }
    find(1);
    find(p);
    printf("%d",( (ans+1)*ans/2)+10*ans); 
    return 0;
}
相关文章
|
3月前
|
人工智能 算法 BI
AcWing 505. 火柴排队(每日一题)
AcWing 505. 火柴排队(每日一题)
|
8月前
|
Java
leetcode-452:用最少数量的箭引爆气球
leetcode-452:用最少数量的箭引爆气球
76 0
|
7月前
|
C语言
C语言----要喝10升水才能解渴,但现在只有一个深 h 厘米,底面半径是 r 厘米的水杯,牛牛最少要喝多少杯水才能解渴
C语言----要喝10升水才能解渴,但现在只有一个深 h 厘米,底面半径是 r 厘米的水杯,牛牛最少要喝多少杯水才能解渴
|
7月前
|
存储 算法 测试技术
力扣经典150题第五十题:用最少数量的箭引爆气球
力扣经典150题第五十题:用最少数量的箭引爆气球
36 0
|
存储
蓝桥杯19国赛-矩阵计数
蓝桥杯19国赛-矩阵计数
95 0
[蓝桥杯 2018 省 B] 螺旋折线
[蓝桥杯 2018 省 B] 螺旋折线
57 0
leetcode 452用最少数量的箭引爆气球
leetcode 452用最少数量的箭引爆气球
93 0
leetcode 452用最少数量的箭引爆气球
LeetCode每日一题(11)——太平洋大西洋水流问题(递归,深度优先遍历实例)
大西洋太平洋水流问题 1.题目 2.示例 3.思路 理解题目 解题思路 4.代码
151 0
LeetCode每日一题(11)——太平洋大西洋水流问题(递归,深度优先遍历实例)
【寒假每日一题】AcWing 4652. 纸张尺寸
目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解
90 0