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; }