Post

baekjoon 1167:트리의 지름

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.