LiveArchive3153

LiveArchiveにログインできない・・・。アカウントを作り直して挑戦。

答えの上限を大まかに見積もっておく。上限の値が出たら、終了。
入力によっては、少しも早くならない気がする・・・。
というか、ACが出たことに驚いた。
実行速度ランキング6位。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;
const int TIME = 420;

int cost[N];
int g[N][N];

int result;
int lim;

void rec(int pos, int vis, int time, int size, int depth)
{
  if( TIME < time )return ;

  result = max( result, depth );
  if( result == lim )return ;

  for(int i=0; i<size; ++i){
    if( vis & (1 << i) ) continue;

    int spend = g[pos][i] + cost[i];
    rec(i, vis | (1 << i), time + spend, size, depth + 1);

    if( result == lim ) return ;
  }
  return ;
}

void wf(int size)
{
  for(int k=0; k<size; ++k){
    for(int i=0; i<size; ++i){
      for(int j=0; j<size; ++j){
        g[i][j] = min( g[i][j], g[i][k] + g[k][j] );
      }
    }
  }
  return ;
}

int main(void)
{
  int n;
  while( cin >> n && n ){

    for(int i=0; i<n; ++i){
      cin >> cost[i];
    }

    for(int i=0; i<n; ++i){
      for(int j=0; j<n; ++j){
        cin >> g[i][j];
      }
    }

    wf(n);
    
    static int c[N];
    copy( cost, cost + n, c );
    
    int mx = 0;
    for(int i=0; i<n; ++i){
      int mn = 1 << 24;
      for(int j=0; j<n; ++j){
        if( i != j ) mn = min(mn, g[i][j]);
      }
      mx = max(mx, mn);
      c[i] += mn;
    }

    sort( c, c + n );
    lim = 0;
    for(int i=0, sum = -mx; i < n && sum + c[i] <= TIME; lim = ++i){
      sum += c[i];
    }

    result = 0;
    for(int i=0; i<n; ++i){
      rec(i, (1 << i), cost[i], n, 1);
    }
    cout << result << endl;
  }
  return 0;
}