2660번 회장뽑기

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

 

INF를 처음에 2e9로 했는데 계속 fw[i][j]의 값이 쓰레기 값으로 출력됐다.

1000으로 수정하니 해결됨.

 

#include <bits/stdc++.h>

using namespace std;

#define MAX 55
#define INF 1000

int fw[MAX][MAX];
int score[MAX];
int n, a, b;
vector<int> v;

int main()
{
    cin.tie(0);

    for (int i = 1; i < MAX; i++) {
        for (int j = 1; j < MAX; j++) {
            fw[i][j] = i == j ? 0 : INF;
        }
    }

    scanf("%d", &n);

    while (true)
    {
        scanf("%d %d", &a, &b);
        if (a == -1 && b == -1) break;
        fw[a][b] = fw[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 (i == j) continue;
                if (fw[i][j] > fw[i][k] + fw[k][j]) { 
                    // INF가 2e9일 때, 오버플로우 발생하는듯
                    fw[i][j] = fw[i][k] + fw[k][j];
                }
            }
        }
    }

    int minValue = INF;
    for (int i = 1; i <= n; i++) {
        int maxValue = 0;
        for (int j = 1; j <= n; j++) {
            maxValue = max(maxValue, fw[i][j]);
        }
        minValue = min(minValue, maxValue);
        score[i] = maxValue;
    }

    for (int i = 1; i <= n; i++) {
        if (minValue == score[i]) {
            v.push_back(i);
        }
    }

    printf("%d %d\n", minValue, v.size());
    for (auto i : v) printf("%d ", i);
    printf("\n");

    return 0;
}