2016년 4월 6일 수요일

2660 - 회장 뽑기

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

친구의 친구 사이는 친구이므로, 각 사람들에 대해 서로 가장 가까운 정도를 구할 수 있다.

구해진 가까운 정도(최단 경로)들이 가장 작은 사람들의 리스트를 만들어 출력한다.

#include <cstdio>

#define INF 987654321

int main(){
    int i, j, k, n;
    int g[101][101];
    scanf("%d ", &n);
 
    for(i=0; i<n; ++i)
        for(j=0; j<n; ++j)
            g[i][j] = i==j?0:INF;
 
    int a, b, c;
    while(~scanf("%d %d ", &a, &b) && a>0)
        g[a-1][b-1] = g[b-1][a-1] = 1;
 
    for(k=0; k<n; ++k){
        for(i=0; i<n; ++i){
            for(j=0; j<n; ++j){
                if(g[i][k]+g[k][j] < g[i][j])
                    g[i][j] = g[i][k]+g[k][j];
            }
        }
    }
 
    int len=0, cand[50]={}, minR=INF;
    for(i=0; i<n; ++i){
        int maxi = 0;
        for(j=0; j<n; ++j)
            if(maxi < g[i][j]) maxi=g[i][j];
  
        if(maxi <= minR){
            if(maxi != minR) len=0;
            cand[len++] = i+1;
            minR = maxi;
        }
    }
 
    printf("%d %d\n", minR, len);
    for(i=0; i<len; ++i) printf("%d ", cand[i]);
 
    return 0;
}
댓글 쓰기

게시글 목록