(1967) 트리의 지름

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

단계별로 풀어보기

33단계(트리) 3번째

 

 

 

입력 형식이나 n=1일 때 예외처리를 빼면 이전 문제와 완전히 동일하다.

아무래도 문제 비고란을 보면 이전 문제는 모든 간선의 가중치가 1이여서 단순 DFS, BFS로 풀리고

이 문제는 가중치가 있어 다익스트라로 풀어야 하는 게 의도인 것 같은데, 이전 문제를 잘못 설정한 것 같다.

 

 

 

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

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

  int n;
  
  cin >> n;
  
  if(n==1){
    cout << 0;
    
    return 0;
  }
  
  vector adj(n+1, vector<p> ());
  vector<int> dist(n+1, INF);
  priority_queue<p, vector<p>, greater<p>> pq;
  
  for(int i=1;i<n;i++){
    int a, b, c;
    
    cin >> a >> b >> c;
    
    adj[a].push_back({c, b});
    adj[b].push_back({c, a});
  }
  
  auto dijk= [&](int start){
    dist= vector<int> (n+1, INF);
    
    dist[start]= 0;
    pq.push({0, start});
    
    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});
        }
      }
    }
  };
  
  dijk(1);
  
  int maxval= 0, maxidx= 0;

  for(int i=1;i<=n;i++){
    if(maxval<dist[i]){
      maxval= dist[i];
      maxidx= i;
    }
  }
  
  dijk(maxidx);
  
  int ans= 0;
  
  for(int i=1;i<=n;i++)  ans= max(ans, dist[i]);
  
  cout << ans;
  
  return 0;
}