UVa 11792 : Krochanska is Here!

問題リンク：http://uva.onlinejudge.org/external/117/11792.html

問題概要：
N個の駅が1からNまでで番号付けされている
路線の情報がS行以下の形式で与えられる
a b c d ... g 0
0は路線の終了を意味する
a b c d gは駅の番号を表す
各駅は路線の1つ前と１つ後ろの駅とつながっている
つまり、上の例でいう駅cは駅bと駅dとつながっている
駅同士の移動にかかるコストは全て等しい
複数の路線に現れる駅を重要な駅という
重要な駅から別の全ての重要な駅に移動するためにかかるコストの平均が最小となる駅の番号を出力せよ
複数存在する場合は駅の番号が最も小さいものを出力せよ

制約：
重要な駅は最大でも１００個まで

解法：
ワーシャルフロイドで解いた
重要な駅は１００個しかないのでそれらをグラフにしてFW

ちなみにpriority_queueを使ったdijkstraだとTLEする

コード：

#include<iostream>
#include<algorithm>
#include<queue>
#include<iomanip>
#include<vector>
#include<cmath>
#include<cassert>
#include<cstdio>
#include<map>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define all(n) (n).begin(),(n).end()
#define inf (1<<29)
#define MAX 10010

using namespace std;


int V,S;
int FW[200][200];

int main()
{
  int T;
  while(scanf("%d",&T) != EOF)
    {
      while(T--)
	{
	  scanf("%d %d",&V,&S);
	  rep(i,101)rep(j,101)FW[i][j] = ((i==j)?0:inf);
	  int counter[V];
	  bool used[V];
	  rep(i,V)
	    {
	      counter[i] = 0;
	      used[i] = false;
	    }

	  vector<int> input[S];
	  rep(i,S)
	    {
	      int station,prev = inf;
	      while(true)
		{
		  scanf("%d",&station);
		  station--;
		  if(station == -1)break;
		  input[i].push_back(station);
		  used[station] = true;
		}
	      rep(j,V)
		{
		  if(used[j])counter[j]++;
		  used[j] = false;
		}
	    }	  

	  vector<int> istation;
	  bool importance[V];
	  map<int,int> Index;
	  rep(i,V)
	    {
	      importance[i] = false;
	      if(counter[i] > 1)
		{
		  importance[i] = true;
		  Index[i] = istation.size();
		  istation.push_back(i);
		}
	    }

	  rep(i,S)
	    {
	      int prev = inf;
	      rep(j,input[i].size())
		{
		  int next = input[i][j];
		  if(importance[next])
		    {
		      if(prev == inf)
			{
			  prev = j;
			}
		      else
			{
			  int v = input[i][prev];
			  int i1 = Index[next];
			  int i2 = Index[v];
			  FW[i1][i2] = FW[i2][i1] = min(FW[i1][i2],abs(prev-j));
			  prev = j;
			}
		    }
		}
	    }

	  int n = istation.size();

	  int ans_station,ans_cost;
	  ans_cost = inf;

	  rep(k,n)rep(i,n)rep(j,n)
	    {
	      if(FW[i][k] == inf || FW[k][j] == inf)continue;
	      FW[i][j] = min(FW[i][j],
			     FW[i][k] + FW[k][j]);
	    }

	  rep(i,n)
	    {
	      int cur = istation[i];
	      int cost = 0;
	      bool out = false;
	      rep(j,n)
		{
		  if(i == j)continue;
		  int next = istation[j];
		  if(FW[i][j] == inf)
		    {
		      out = true;
		      break;
		    }
		  cost += FW[i][j];
		}
	      if(out)continue;
	      if(ans_cost == inf)
		{
		  ans_cost = cost;
		  ans_station = cur;
		}
	      else
		{
		  if(ans_cost > cost)
		    {
		      ans_cost = cost;
		      ans_station = cur;
		    }
		  else if(ans_cost == cost)
		    {
		      ans_station = min(ans_station,cur);
		    }
		}
	    }

	  printf("Krochanska is in: %d\n",ans_station+1);
	}
    }
  return 0;
}