POJ--2139 Six Degrees of Cowvin Bacon(最短路)

记录
20:34 2024-2-1

http://poj.org/problem?id=2139

最短路问题，使用Floyd后遍历选择就可以了。注意是多case输入，答案截尾。

#include<cstdio>
#include<cstring>
#include<iostream>
#define MAX_N 305
#define MAX_M 10005
using namespace std;

const int INF = 0x3f3f3f3f;

int N, M;
int graph[MAX_N][MAX_N];

void floyd() {
    for(int k = 1; k <= N; k++) {
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
        }
    }
}

int main() {
    while(scanf("%d%d",&N,&M)!=EOF) {
        memset(graph, INF, sizeof(graph));
        while(M--) {
            int num;
            cin >> num;
            int arr[num];
            for(int i = 0; i < num; i++) cin >> arr[i];
            for(int i = 0; i < num; i++) {
                for(int j = i + 1; j < num; j++) {
                    graph[arr[i]][arr[j]] = 1;
                    graph[arr[j]][arr[i]] = 1;
                }
            }
        }
        floyd();
        float min = INF;
        for (int i = 1; i <= N; i++)  {
            float total = 0;
            float count = 0;
            for (int j = 1; j <= N; j++) {
                if(i != j) {
                    total += graph[i][j];
                    count++;
                }
            }
            if (total / count < min) min = total / count;
        }
        printf("%d\n", (int)(min * 100));
    }
}