POJ 2139 Six Degrees of Cowvin Bacon 最短路

题目链接

Sample Input
4 2
3 1 2 3
2 3 4
Sample Output
100

题目大意：
给定 n, m.
之后m行，每行是一个集合。
每一个集合里任意两个元素之间的距离都是1.
最后求出一个点，这个点到其余所有点的距离和最小，即
求ans令 ∑dis[ans][i] 最小 (1=<i<=n 且i不等于ans)
然后输出平均距离（乘100倍保留整数），
即 sum / (n-1) * 100

解题思路：
奇怪的建表方式+Floyd算法

AC代码：

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int path[301][301];
int worked[301];
#define INF 0x3fffffff
void init() {
    for (int i = 1; i <= 300; i++) {
    for (int j = 1; j <= 300; j++) {
    path[i][j] = INF;}path[i][i] = 0;}
}
int main() {
    int n, m;while (cin >> n >> m) {
    init();while (m--) {
    int num, a;cin >> num;for (int i = 1; i <= num; i++) {
    cin >> worked[i];}for (int i = 1; i < num; i++) {
    for (int j = i + 1; j <= num; j++) {
    path[worked[i]][worked[j]] = 1; path[worked[j]][worked[i]] = 1;}}}for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
    if (path[i][k] == INF || path[k][j] == INF) continue;if (path[i][j] == INF || path[i][j] > path[i][k] + path[k][j]) {
    path[i][j] = path[i][k] + path[k][j];}}}}int ans = INF;for (int k = 1; k <= n; k++) {
    int tmp = 0;for (int l = 1; l <= n; l++) {
    tmp += path[k][l];}ans = min(ans, tmp);}//cout << ans << endl;cout << ans * 100 / (n - 1) << endl;}
}