백준 6118:숨바꼭질

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

이번문제는 간단한 다익스트라 알고리즘문제예요. 문제는 최단거리를 계산하지만! 가장먼곳(최장거리)를 계산하면 되는것이에요. 가장 작은번호 출력 주의!

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
#define INF (static_cast<int>(1e9))
#define endl '\n'
typedef pair<int, int> PAIR;
int main(void) {
    ios::sync_with_stdio(false);
    int N, M; cin >> N >> M;
 
    priority_queue<PAIR, vector<PAIR>, greater<PAIR>> pq;
    vector<vector<int>> graph(N);
    vector<bool> visited(N);
    vector<int> cost(N, INF);
 
    for (int i = 0; i < M; i++) {
        int A_i, B_i; cin >> A_i >> B_i;
        graph[A_i - 1].push_back(B_i - 1);
        graph[B_i - 1].push_back(A_i - 1);
    }
 
    pq.push(PAIR(0, 0));
    cost[0] = 0;
 
    
    while (!pq.empty()) {//다익스트라 알고리즘
        int cur;
        do {
            cur = pq.top().second; pq.pop();
        } while (!pq.empty() && visited[cur]);
 
        if (visited[cur]) break;
        visited[cur] = true;
 
        for (auto& next : graph[cur]) {//거리는 1고정
            if (cost[next] > cost[cur] + 1) {
                cost[next] = cost[cur] + 1;
                pq.push(PAIR(cost[next], next));
            }
        }
    }
 
    int where = 0, maximum = 0, cnt = 0;
    for (int i = 0; i < N; i++) {//위치와 거리, 갯수를 계산해요
        if (cost[i] > maximum) {
            where = i;
            maximum = cost[i];
            cnt = 1;
        }
        else if (cost[i] == maximum) cnt++;
    }
 
    cout << where + 1 << ' ' << cost[where] << ' ' << cnt << endl;
 
    return 0;
}