2660 회장뽑기

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

회원의 점수는 나머지 회원들까지 최단 거리의 최대값이다. 이 때 회원의 수가 최대 50명이므로 플로이드로 간편하게 구할 수 있다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int n,i,j,k,d[51][51],p[51],minv=100;
 
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++) for(j=1;j<=n;j++)
        if(i!=j) d[i][j]=100;
    while(true)
    {
        scanf("%d %d",&i,&j);
        if(i==-1 && j==-1) break;
        d[i][j]=d[j][i]=1;
    }
    for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++)
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    for(i=1;i<=n;i++)
    {
        int m=0;
        for(j=1;j<=n;j++) if(d[i][j]!=100) m=max(m,d[i][j]);
        p[i]=m;
        minv=min(minv,m);
    }
    vector<int> v;
    int cnt=0;
    for(i=1;i<=n;i++) if(p[i]==minv) cnt++,v.push_back(i);
    printf("%d %d\n",minv,cnt);
    for(i=0;i<cnt;i++) printf("%d ",v[i]);
    return 0;
}