(BOJ) 6118 숨바꼭질

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

문제 풀이:

- 다익스트라 돌려서 1에서 각 점까지의 최단 거리 구함

- 구해놓은 dist를 처음부터 끝까지 보면서 제일 큰 수와 그 수의 개수를 찾음

소스 코드:

#include <iostream> #include <queue> #include <vector> #include <string.h> #include <algorithm> #define inf 987654321 using namespace std; typedef pair<int, int> P; int n, m,dist[20001],t,cnt; bool visit[20001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> m; vector<vector<int>> adj; adj.resize(n + 1); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } fill(dist, dist + n + 1, inf); priority_queue<P> pq; dist[1] = 0; pq.push({ 0,1 }); while (!pq.empty()) { int cur; do { cur = pq.top().second; pq.pop(); } while (!pq.empty() && visit[cur]); if (visit[cur]) break; visit[cur] = true; for (auto& i : adj[cur]) { if (dist[i] > dist[cur] + 1) { dist[i] = dist[cur] + 1; pq.push({ -dist[i],i }); } } } dist[0] = 0; for (int i = 1; i <= n; i++) { if (dist[t] < dist[i]) { t = i; cnt = 1; } else if (dist[t] == dist[i]) cnt++; } cout << t << " " << dist[t] <<" "<< cnt << '\n'; return 0; }