POJ-2139 : Six Degrees of Cowvin Bacon

問題概要

連結グラフが与えられる。ある点を中心とした距離の近いほうN個の平均長の最小値を求める問題。

解法

真面目に幅優先で求めて十分間に合う。

acceptされたコード

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_N = 302;
const int MAX_M = 10002;
const int INF = 1<<29;
int N, M;
vector<int> graph[MAX_N+MAX_M];
bool visited[MAX_N + MAX_M];

int solve(){
	int best = INF;
	for(int i=0; i<N; i++){
		memset(visited, 0, sizeof(visited));
		queue< pair<int, int> > que;
		que.push( make_pair(i, 0) );
		visited[i] = true;

		int cnt = 0;
		while(!que.empty()){
			pair<int,int> tp = que.front(); que.pop();
			int cur = tp.first, d = tp.second;
			if(cur < N) cnt += d/2;
			for(int j=0; j<(int)graph[cur].size(); j++){
				int next = graph[cur][j];
				if(!visited[next]){
					visited[next] = true;
					que.push( make_pair(next, d+1) );
				}
			}
		}
		best = min(best, cnt);
	}

	return best*100/(N-1);
}

int main(){
	scanf("%d%d",&N,&M);
	for(int i=0; i<M; i++){
		int K; scanf("%d",&K);
		for(int j=0; j<K; j++){
			int x; scanf("%d",&x);
			graph[x-1].push_back(N + i);
			graph[N+i].push_back(x-1);
		}
	}
	printf("%d\n",solve());
	return 0;
}