(1167) 트리의 지름

https://www.acmicpc.net/problem/1167

단계별로 풀어보기

33단계(트리) 2번째

 

 

 

트리의 지름을 구하려면 두 단계를 거쳐야 한다.

1. 임의의 노드에서 다익스트라를 돌려 가장 먼 노드를 찾는다.

2. 1에서 찾은 가장 먼 노드에서 다시 다익스트라를 돌린다. 이때 가장 먼 노드와의 거리가 트리의 지름이다.

수학적인 증명은 있지만 자세한 것은 생략한다. 임의의 노드에서 찾은 가장 먼 노드는 지름의 한 끝에 해당하는 노드이다.(원 내부의 한 점에서 가장 먼 점은 원의 경계 위의 점이라는 것으로 생각하면 된다.) 이제 그 노드에서 가장 먼 점과의 거리가 트리의 지름이 된다.

 

 

 

#include <iostream>
#include <queue>
using namespace std;
typedef pair<int,int> p;
#define INF 1000000001

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int v, ans= 0;
  
  cin >> v;
  
  vector adj(v+1, vector<p> ());
  vector<int> dist(v+1, INF);
  priority_queue<p, vector<p>, greater<p>> pq;
  
  for(int i=0;i<v;i++){
    int a;
    
    cin >> a;
    
    while(true){
      int b, c;
      
      cin >> b;
      
      if(b==-1)  break;
      
      cin >> c;
      
      adj[a].push_back({c, b});
    }
  }
  
  dist[0]= 0;
  pq.push({0,1});
  
  while(!pq.empty()){
    p now= pq.top();
    pq.pop();
    
    if(now.first>dist[now.second])  continue;
    
    for(p next:adj[now.second]){
      if(now.first+next.first<dist[next.second]){
        dist[next.second]= now.first+next.first;
        pq.push({now.first+next.first, next.second});
      }
    }
  }

  for(int i=2;i<=v;i++)  ans= max(ans, dist[i]);
  
  cout << ans;
  
  return 0;
}