1 solutions
-
0
#include<bits/stdc++.h> using namespace std; const int N=1e5+10,INF=0x3f3f3f3f; int n,m; typedef pair<int,int> PII; #define x first #define y second vector<PII> g[N]; int dist[N]; void dfs(int u,int father) //往下传递 { for(auto k:g[u]) { if(k.x==father) continue; //往回搜索 dist[k.x]=dist[u]+k.y; //更新记录 dfs(k.x,u); //继续往下传递 } } int main() { cin>>n; for(int i=0;i<n-1;i++) //获取树 { int a,b,c; cin>>a>>b>>c; g[a].push_back({b,c}); g[b].push_back({a,c}); } dfs(1,-1); int u=1; //找到最大距离 for(int i=1;i<=n;i++) { if(dist[i]>dist[u]) { u=i; } } dist[u]=0; dfs(u,-1); int v=1;//最远距离 for(int i=1;i<=n;i++) { if(dist[i]>dist[v]) { v=i; } } cout<<dist[v]; return 0; }
- 1
Information
- ID
- 2137
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 5
- Tags
- (None)
- # Submissions
- 12
- Accepted
- 6
- Uploaded By