baekjoon 1167:트리의 지름
1167번 트리의 지름
접근
핵심은 1967번과 같다. 단지 크기가 늘어나서 long long int로 바꿔줘야할 뿐이다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <vector>
#include <array>
using namespace std;
void dfs(vector<vector<pair<int, int>>>& v, int x, vector<long long int>& dist);
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n; cin >> n;
vector<vector<pair<int, int>>> v(n);
vector<long long int> dist(n, -1);
for(int i = 0; i < n; i++){
int num; cin >> num;
while(true){
int a, b; cin >> a;
if(a == -1) break;
cin >> b;
v[num-1].push_back({a-1, b});
}
}
// for(int i = 0; i < n; i++){
// for(auto j : v[i]){
// cout << "(" << j[0] << ", " << j[1] << ")";
// }
// cout << endl;
// }
dist[0] = 0;
dfs(v, 0, dist);
int u = 0;
long long int max = 0;
for(int i = 0; i < n; i++){
if(dist[i] > max){
max = dist[i];
u = i;
}
}
fill(dist.begin(), dist.end(), -1);
dist[u] = 0;
dfs(v, u, dist);
long long int max2 = 0;
for(int i = 0; i < n; i++){
if(dist[i] > max2){
max2 = dist[i];
}
}
cout << max2;
return 0;
}
void dfs(vector<vector<pair<int, int>>>& v, int x, vector<long long int>& dist){
for(auto& i : v[x]){
if(dist[i.first] == -1){
dist[i.first] = dist[x] + (long long int)i.second;
dfs(v, i.first, dist);
}
}
}
This post is licensed under CC BY 4.0 by the author.