[백준 1967] 트리의 지름

아래의 논리를 알면 풀기 쉽다.

 

아무 정점이나 잡아서 그 정점과 다른 노드들 간의 최단거리를 구했을때 가장 멀리 있는 노드가

트리의 지름을 구성하는 노드 중 하나라는 것이다.

 

따라서 일단 아무 정점에서 가장 멀리 있는 정점을 찾고

해당 정점으로 또 다익스트라를 돌려서 가장 멀리 있는 정점간의 거리를 구하면 그게 바로 트리의 지름이다.

 

---

#include <iostream>
#include <vector>
#include <queue>

#define SIZE 100001
#define INF int(1e9)

using namespace std;

int V;
vector<vector<pair<int, int>>> graph(SIZE);

// 그냥 1부터 시작해서 찾기
int findFarthestPoint(){
    int dist[SIZE];
    for (int i = 1; i <= V;i++){
        dist[i] = INF;
    }
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, 1));
    dist[1] = 0;

    while(!pq.empty()){
        auto [total, cur] = pq.top();
        pq.pop();

        if(total > dist[cur])
            continue;

        for (int i = 0; i < graph[cur].size();i++){
            int next = graph[cur][i].first;
            int cost = graph[cur][i].second;

            // 조사할만한거 조사해보기
            if(total + cost < dist[next]){
                dist[next] = total + cost;
                pq.push(make_pair(total + cost, next));
            }
        }
    }

    int ans = 1;
    for (int i = 1; i <= V;i++){
        if(dist[i] > dist[ans]){
            ans = i;
        }
    }

    return ans;
}

void solve(int node1){
    int dist[SIZE];
    for (int i = 1; i <= V;i++){
        dist[i] = INF;
    }
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, node1));
    dist[node1] = 0;

    while(!pq.empty()){
        auto [total, cur] = pq.top();
        pq.pop();

        if(total > dist[cur])
            continue;

        for (int i = 0; i < graph[cur].size();i++){
            int next = graph[cur][i].first;
            int cost = graph[cur][i].second;

            // 조사할만한거 조사해보기
            if(total + cost < dist[next]){
                dist[next] = total + cost;
                pq.push(make_pair(total + cost, next));
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= V; i++)
    {
        if(dist[i] > ans){
            ans = dist[i];
        }
    }

    cout << ans;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> V;
    int start, end, cost;
    for (int i = 0; i < V; i++)
    {
        cin >> start;
        while(1){
            cin >> end;
            if(end==-1)
                break;
            cin >> cost;
            graph[start].push_back(make_pair(end, cost));
            graph[end].push_back(make_pair(start, cost));
        }
    }

    int node1 = findFarthestPoint();
    // cout << node1 << "\n";
    solve(node1);

    return 0;
}