Description
很久以前, T 王国空前繁荣. 为了更好地管理国家, 王国修建了大量的快速路, 用于连接首都和王国内的各大城市.
为节省经费, T 国的大臣们经过思考, 制定了一套优秀的修建方案, 使得任何一个大城市都能从首都直接或者通过其他大城市间接到达. 同时, 如果不重复经过大城市, 从首都到达每个大城市的方案都是唯一的.
J 是 T 国重要大臣, 他巡查于各大城市之间, 体察民情. 所以, 从一个城市马不停蹄地到另一个城市成了 J 最常做的事情. 他有一个钱袋, 用于存放往来城市间的路费.
聪明的 J 发现, 如果不在某个城市停下来修整, 在连续行进过程中, 他所花的路费与他已走过的距离有关, 在走第 x 千米到第 x+1 千米这一千米中 (x 是整数), 他花费的路费是 x+10 这么多. 也就是说走 1 千米花费 11, 走 2 千米要花费 23.
J 大臣想知道: 他从某一个城市出发, 中间不休息, 到达另一个城市, 所有可能花费的路费中最多是多少呢?
Input
输入的第一行包含一个整数 n, 表示包括首都在内的 T 王国的城市数
城市从 1 开始依次编号, 1 号城市为首都.
接下来 n-1 行, 描述 T 国的高速路 (T 国的高速路一定是 n-1 条)
每行三个整数 Pi, Qi, Di, 表示城市 Pi 和城市 Qi 之间有一条高速路, 长度为 Di 千米.
Output
输出一个整数, 表示大臣 J 最多花费的路费是多少.
Sample Input
样例输入 1
- 5
- 1 2 2
- 1 3 1
- 2 4 5
- 2 5 4
- Sample Output
样例输出 1 135
Source
蓝桥杯
传送门: https://acmore.cc/problem/LOCAL/1602
分析:
题目其实是要你求任意两点间的最长路, 图其实是一棵树, 那么就是求树的直径
假设树的最长路是 s-t, 也就是树的直径
那么从任意一点 u 出发找到的最长路的端点 x 一定是 s 或者 t 中的一点, 然后从 x 出发再找最长路, 找到的路径就是树的直径!
所以第一次从任意点 u 开始 dfs 找最长路径的端点 x, 然后从 x 开始 dfs 找到树的直径
- code:
- #include<bits/stdc++.h>
- using namespace std;
- #define max_v 100005
- struct node
- {
- int v,c;
- node(int x,int y)
- {
- v=x;
- c=y;
- }
- };
- vector<node> G[max_v];
- int n;
- int ans,s1;
- int vis[max_v];
- void init()
- {
- memset(vis,0,sizeof(vis));
- ans=-1;
- }
- void dfs(int u,int sum)
- {
- if(sum>ans)
- {
- ans=sum;
- s1=u;
- }
- for(int i=0;i<G[u].size();i++)
- {
- int v=G[u][i].v;
- int w=G[u][i].c;
- if(vis[v]==0)
- {
- vis[v]=1;
- dfs(v,sum+w);
- vis[v]=0;
- }
- }
- }
- int main()
- {
- cin>>n;
- int x,y,z;
- for(int i=1;i<=n-1;i++)
- {
- cin>>x>>y>>z;
- G[x].push_back(node(y,z));
- G[y].push_back(node(x,z));
- }
- init();
- vis[1]=1;
- dfs(1,0);
- init();
- vis[s1]=1;
- dfs(s1,0);
- long long sum=0;
- for(int i=1;i<=ans;i++)
- {
- sum+=(i+10);
- }
- cout<<sum<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2981043.html