백준: Class 4 - 1167, 1238

</br> 이제 클래스 4다 골드 5, 4, 3이 많다!!
40문제 풀어야 하니까 오늘은 17일이니 22일까지 끝내기로 하자
</br>

1167: 트리의 지름

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

void func(int now, int d){
    visited[now] = 1;
    if( d > ans ){
        ans = d;
        r = now;
    }
    for(int i = 0; i < tree[now].size(); i++){
        if( visited[tree[now][i].second] == 0 ){
            func(tree[now][i].second, tree[now][i].first + d);
        }
    }
}

// in main()
    func(1, 0);
    for(int i = 1; i <= n; i++){
        visited[i] = 0;
    }
    func(r, 0);
    cout << ans << endl;

알고리즘 수업 시간에 배웠는데, 머리끄댕이 알고리즘이라 가르쳐 주셨다
트리에서 한 노드를 잡고 쭉 늘어뜨리면, 가장 먼 노드가 나올 거다.
그 노드를 잡고 쭉 늘어뜨리면, 가장 먼 노드가 된다.

트리의 지름이 되는 a, b가 있고 임의의 c를 고르자
a ---c---------- b

c를 잡고 늘이면
  /---a
c<
  \----------b 
따라서 c에서 가장 먼 노드는 b

b를 잡고 늘이면
b ----------c---a

대충 이런 식으로 가능하다
간선에 가중치가 없으면 bfs로 하는데, 이 문제는 있으니까 dfs로 했다.
</br>

참고로 같은 클래스 4 문제인데, 1967: 트리의 지름(https://www.acmicpc.net/problem/1967)은 입력만 다르고 똑같은 문제다
</br>

1238: 파티

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

void func(int arr[1001], int start){
    for(int i = 1; i <= n; i++){
        arr[i] = 10000001;
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    arr[start] = 0;
    pq.push(make_pair(0, start));
    while( pq.size() ){
        int d = pq.top().first;
        int now = pq.top().second;
        pq.pop();
        if( d > arr[now] ) continue;
        for(int i = 0; i < graph[now].size(); i++){
            int nd = graph[now][i].first;
            int nx = graph[now][i].second;
            if( nd+d < arr[nx] ){
                arr[nx] = nd+d;
                pq.push(make_pair(arr[nx], nx));
            }
        }
    }
}

// in main()
    func(ansdist, x);
    for(int i = 1; i <= n; i++){
        if( i == x ) continue;
        func(dist, i);
        ansdist[i] += dist[x];
    }
    cout << *max_element(ansdist, ansdist+n+1) << '\n';

다익스트라로 최단거리 몇 번 구해주면 된다
x에서 다른 데까지의 거리를 일단 구해서 답 배열에 저장하고, 각 마을에서 x까지의 거리를 구해서 답 배열에 더해준다.
최댓값을 출력하면 끝

ex) 백준 예제
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

x = 2에서 거리
1 0 3 7

1: 0 4 2 6 >> 4
3: 2 6 0 4 >> 6
4: 4 3 6 0 >> 3

따라서 5, 0, 9, 10

</br>

---

인덱스는 또 길어질 거 같으니까 떼야겠다
</br>