1389번: 케빈 베이컨의 6단계 법칙

#include <cstdio>
#include <algorithm>
using namespace std;
#define inf 1000000000
int main()
{ 
	int n, m, route[101][101], a, b, ans = 1;
	fill_n(&route[0][0], 101 * 101, inf);
	for (scanf("%d %d", &n, &m); m--; route[a][b] = 1, route[b][a] = 1)
		scanf("%d %d", &a, &b);
	for (int i = 1; i <= n; ++i)
		route[i][0] = 0;
	for (int k = 1; k <= n; ++k)
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j)
				route[i][j] = min(route[i][j], route[i][k] + route[k][j]);
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if (i == j)
				continue;
			if (route[i][j] < inf)
				route[i][0] += route[i][j];
		}
		if (route[ans][0] > route[i][0])
			ans = i;
	}
	printf("%d", ans);
}