11792 - Krochanska is Here!

問題概要

複数の路線が与えられ、ある駅が複数の路線に含まれるような駅を"important station"という。各important stationについて、他のimportant stationへ行く最短時間の平均が最小になるようなimportant stationを求めよう。ただし、それが複数ある場合は、IDの小さいものとする。

コード

#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#define INF (1<<22)

using namespace std;

struct node{
  int w;
  int cnt;
  vector<int> vcon;
  node():w(INF),cnt(0){}
};

typedef vector<node> graph;

void BFS( graph &G, int st ){
  queue<int> q;
  bool visited[G.size()+1];
 
  fill(visited,visited+G.size()+1,false);
  visited[st]=true;
  q.push( st );
  while( !q.empty() ){
    int now = q.front();
    q.pop();

    for(unsigned int i = 0; i < G[ now ].vcon.size(); ++i){
      int next = G[ now ].vcon[i];
      if( !visited[ next ]  ){
	visited[ next ] = true;
	q.push( next );
	G[ next ].w = G[ now ].w + 2;
      }
    }
  }
}

int main(){
  int T;

  cin >> T;
  for(int tc=1; tc<=T; ++tc){
    int ans;
    int minsum = INF;
    graph G;
    int N,S;

    cin >> N >> S;
    int cnt[N+1];
    fill(cnt,cnt+N+1,0);
    G.resize(N+1);
    for(int i = 0; i < S; ++i){
      int src;
      cin >> src;
      cnt[src]++;
      while(true){
	int dst;
	cin >> dst;
	if( dst == 0 ) break;
	G[src].vcon.push_back(dst);
	G[dst].vcon.push_back(src);
	src = dst;
	cnt[dst]++;
      }
    }

    for(unsigned int i = 1; i < G.size(); ++i){
      if( cnt[i] > 1 ){
	int sum = 0;
	G[i].w = 0;
	BFS( G, i );
	for(unsigned int j = 1; j < G.size(); ++j){
	  if( cnt[j] > 1 ){
	    sum += G[j].w;
	  }
	}
	if( sum < minsum ){
	  minsum = sum;
	  ans = i;
	}else if(sum == minsum && i < ans ){
	  ans = i;
	}
      }
    }

    cout << "Krochanska is in: " << ans << endl;

  }
  return 0;
}

解法

コストが固定だから、各important stationを始点にBFSする。計算量は100*10000くらいだと思うが、なんとか間に合う。