[C++] BOJ 6118 - 숨바꼭질

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

vector<pair<int, int>> graph[20001];
int n,m;

vector<int> dijkstra(int start, int V) { 
	vector<int> dist(V, INT_MAX);
	dist[start] = 0;
	
	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, start));
	
	while(!pq.empty()) {
		int cost = -pq.top().first;
		int here = pq.top().second;
		
		pq.pop();
		
		if(dist[here] < cost) continue;
		
		for(int i=0;i<graph[here].size();i++) {
			int nextPos = graph[here][i].first;
			int nextDist = cost + graph[here][i].second;
			
			if(dist[nextPos] > nextDist) {
				dist[nextPos] = nextDist;
				pq.push(make_pair(-nextDist, nextPos));
			}
		}
	}
	
	return dist;
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	
	cin >> n >> m;
	n++;
	
	while(m--) {
		int from, to;
		
		cin >> from >> to;
		graph[from].push_back(make_pair(to, 1));
		graph[to].push_back(make_pair(from, 1));
	}
	
	vector<int> vv = dijkstra(1, n);
	int ans = 0, ansNum = n, gaesu = 0;
	
	for(int i=n-1;i>=2;i--) {
		if(ans <= vv[i]) {
			ans = vv[i];
			ansNum = i;
		}
	}
	
	for(int i=2;i<n;i++) 
		if(ans == vv[i]) gaesu++;
	
	cout << ansNum << " " << ans << " " << gaesu;
}

다익스트라 문제입니다.

서로 연결된 정점들을 입력받고 그 간선의 길이를 1이라고 두고, 1번 정점으로부터 가장 먼 정점의 번호와 그 길이, 그리고 먼 정점으로터의 거리와 같은 다른 정점들을 출력하면 되겠습니다.

다익스트라 문제를 다시금 복습하게 해주는 문제였습니다.