[백준 6118] 숨바꼭질

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

6118번: 숨바꼭질

 

요구사항

시작 정점에서 부터 제일 거리가 먼 정점의 길이 구하기

 

풀이

다익스트라 풀이

 

시작 정점의 거리는 1로 초기화하는게 아니라 0으로 초기화 한다

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
#define p pair<int,int>
struct go {
	int x;
	int y;
};
bool com(go a, go b) {
	if (a.x > b.x) {
		return true;
	}
	else if (a.x == b.x) {
		if (a.y < b.y) {
			return true;
		}
	}
	return false;
}

bool com1(go a, go b) {
	if (a.x > b.x) {
		return true;
	}
	return false;
}
go dist[20020];
vector<int> v[20020];
int n, m;
int ans;
vector<p> vans;
int visit[20020];
int main(){
	scanf("%d%d", &n, &m);

	for (int i = 1; i <= 20019; i++)
	{
		dist[i].x = 987654321;
		dist[i].y = i;
	}

	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	priority_queue<pair<int, int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
	q.push({ 0,1 });
	visit[1] = 1;
	dist[1].x = 0;

	while (!q.empty()) {
		
		int nowdist = q.top().first;
		int nownode = q.top().second;
		q.pop();
		if (dist[nownode].x < nowdist) continue;
		for (int i = 0; i < v[nownode].size(); i++) {
			int nextvalue = v[nownode].at(i);
			int nextdist = nowdist + 1;
			if (dist[nextvalue].x > nextdist) {
				dist[nextvalue].x = nextdist;
				q.push({ nextdist,nextvalue });
			}
		}
	}
	//cout << "A" << endl;
	int ansresult = 1;
	int anscnt = 1;
	//sort(dist + 1, dist + n + 1, com1);
	for (int i = 2; i <= n; i++) {
		//cout << dist[i].x << " ";
		if (dist[ansresult].x < dist[i].x) {
			//cout << "B" << endl;
			anscnt = 1;
			ansresult = i;
		}
		else if (dist[ansresult].x == dist[i].x) {
			anscnt++;
			//cout << "A" << endl;
			//cout << anscnt << endl;
		}
	}
	cout << ansresult << " " << dist[ansresult].x << " " << anscnt << "\n";
	



}