[C++]숨바꼭질[백준 6118]

문제 설명에서 가장 먼거리에 숨은 헛간의 번호를 찾는다고 하였으나 사실상 시작점으로 부터
각 헛간까지 우회하는 경로가 없어야하므로, 다익스트라로 각 헛간까지의 최단거리를 
갱신해주면된다. 

중요한것은 거리를 기준으로 정렬하였을때, 초기 입력받은 번호에 대한 정보를 잃지 않기 위해서 

구조체 형식으로 거리배열을 생성하고, 갱신하였다. 

나머지는 무방향 그래프이면서 최대거리와 최대거리 요소의 갯수만 찾아주면 간단히 해결된다.

<code>

//pda_pro12
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
 
#define all(x) x.begin(), x.end()
#define INT 0x7fffffff
#define N_ 20001
 
using namespace std;
 
struct DATA { int num, value; };
 
vector<pair<int, int>> v[N_]; priority_queue<pair<int, int>> pq;
int n, m; DATA dst[N_]; int x, y; vector<int> ans;
 
bool cmp(DATA u, DATA t) {
    return u.value < t.value;
}
bool cmp1(DATA u, DATA t) {
    return u.num < t.num;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
    while (m--) {
        cin >> x >> y;
        v[x].push_back({ y, 1 });
        v[y].push_back({ x, 1 });
    }
    for (int i = 1; i <= n; i++) {
        dst[i].value = INT, dst[i].num = i;
    }
    dst[1].value = 0;
    pq.push({ 1, 0 });
    while (!pq.empty()) {
        int v_x = pq.top().first;
        int dis = -pq.top().second;
        pq.pop();
        if (dis > dst[v_x].value) continue;
        for (int i = 0; i < v[v_x].size(); i++) {
            int next = v[v_x][i].first;
            int n_dis = dis + v[v_x][i].second;
            if (n_dis < dst[next].value) {
                dst[next].value = n_dis;
                pq.push({ next, -n_dis });
            }
        }
    }
    sort(dst + 1, dst + 1 + n, cmp);
    int Max = 0;
    for (int i = 1; i <= n; i++) {
        if (Max < dst[i].value) {
            Max = dst[i].value;
            ans.clear();
            ans.push_back(dst[i].num);
        }
        else if (Max == dst[i].value)
            ans.push_back(dst[i].num);
    }
    sort(all(ans));
    cout << ans.front() << ' ' << Max << ' ' << ans.size();
 
    return 0;
}