在山上一共有N個站點需要檢查，檢查員從山頂出發(fā)去各個站點進行檢查，各個站點間有且僅有一條通路，檢查員下山前往站點時比較輕松，而上山時卻需要額外的時間，問最后檢查員檢查完所有站點時所需要的額外時間最少是多少。

Input
包含多組數(shù)據(jù) 每組數(shù)據(jù)輸入第一行為一個整數(shù)N 表示站點個數(shù)（1<=N<=100000）,接下去N-1 行 每行3個整數(shù) x，y，z(1<=z<=10000) 檢查站x為檢查站y的父節(jié)點，x,y之間有一條通路，從y到x需要額外z的時間。（父節(jié)點在子節(jié)點上方，山頂固定標號為1）
Output
輸出一行一個整數(shù)表示最少需要花費的額外時間。
Sample Input
6
1 2 1
2 4 1
1 3 1
3 5 1
3 6 1
Sample Output
3
思路： 先求和 總的減去
代碼；

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; struct stu{int sum;stu(){sum=0;} }; int main() {stu s[200000];int n,x,y,z;while(~scanf("%d",&n)){int max=0,ans=0;for(int i=1;i<n;i++){scanf("%d%d%d",&x,&y,&z);ans=ans+z;s[y].sum=s[x].sum+z;if(max<s[y].sum)max=s[y].sum;}printf("%d\n",ans-max);}return 0; }

總結

以上是生活随笔為你收集整理的检查站点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。