1 条题解
-
0
Guest
-
0
#include<bits/stdc++.h> #include<vector> #include<queue> #include<algorithm> using namespace std; int n,u,v,w,k,sum; struct edge{int x,y;}; vector<edge> a[200001]; int bfs(int s){ int maxn = s; int tr[100002]; memset(tr, 0 ,sizeof(tr)); tr[s] = 1; queue<int> q; q.push(s); while(!q.empty()){ int l = q.front(); q.pop(); for(int i = 0;i < a[l].size();i++){ if(tr[a[l][i].x] == 0){ q.push(a[l][i].x); tr[a[l][i].x] = tr[l] + a[l][i].y; if(tr[maxn] < tr[a[l][i].x]){ maxn = a[l][i].x; } } } } sum = tr[maxn] - 1; return maxn; } int main(){ scanf("%d",&n); k = n; while(--n){ scanf("%d%d%d",&u,&v,&w); a[u].push_back({v,w}); a[v].push_back({u,w}); } bfs(bfs(1)); printf("%d",sum); return 0; }
两次bfs就可以了,easy
- 1
信息
- ID
- 8346
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 16
- 已通过
- 5
- 上传者