백준 2660 회장뽑기

문제링크

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

문제

키포인트

전형적인 플로이드 와샬문제

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define INF 101
int floid[51][51];
int main() {
	int n;
	cin >> n;

	fill(&floid[0][0], &floid[50][51], INF);
	while (true) {
		int a, b;
		cin >> a >> b;
		if (a == -1 && b == -1) break;
		floid[a][b] = 1;
		floid[b][a] = 1;
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (floid[i][k] + floid[k][j] <floid[i][j]) {
					floid[i][j] = floid[i][k] + floid[k][j];
				}
			}
		}
	}

	vector<int> ans;
	int minst[51], totalmin = INF;
	fill(minst, minst + 51, INF);
	for (int i = 1; i <= n; i++) {
		int minn = 0;
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			minn = max(minn, floid[i][j]);
		}
		minst[i] = minn;
		totalmin = min(minn, totalmin);
	}

	for (int i = 1; i <= n; i++) {
		if (minst[i] == totalmin) ans.push_back(i);
	}

	cout << totalmin << ' ' << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++) cout << ans[i] << ' ';
}

추가

전형적인 플로이드 와샬 대표문제인데 한동안 안풀다보니 또 생각을 못했다.
복습하자. 나동빈님이 작성하신 글에 플로이드 와샬 설명이 잘되어있다.
https://blog.naver.com/ndb796/221234427842