SRM452Div2

SRM451Div2

SRM450Div2

SRM349Div2

SRM348Div2

UVa811

全部試す。やるだけ。

SRM347Div2

SRM346Div2

SRM345Div2

SRM344Div2

SRM343Div2

LiveArchive3153

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

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

view plainprint?

1. #include <iostream>  
2. #include <algorithm>  
3.   
4. using namespace std;  
5.   
6. const int N = 20;  
7. const int TIME = 420;  
8.   
9. int cost[N];  
10. int g[N][N];  
11.   
12. int result;  
13. int lim;  
14.   
15. void rec(int pos, int vis, int time, int size, int depth)  
16. {  
17.   if( TIME < time )return ;  
18.   
19.   result = max( result, depth );  
20.   if( result == lim )return ;  
21.   
22.   for(int i=0; i<size; ++i){  
23.     if( vis & (1 << i) ) continue;  
24.   
25.     int spend = g[pos][i] + cost[i];  
26.     rec(i, vis | (1 << i), time + spend, size, depth + 1);  
27.   
28.     if( result == lim ) return ;  
29.   }  
30.   return ;  
31. }  
32.   
33. void wf(int size)  
34. {  
35.   for(int k=0; k<size; ++k){  
36.     for(int i=0; i<size; ++i){  
37.       for(int j=0; j<size; ++j){  
38.         g[i][j] = min( g[i][j], g[i][k] + g[k][j] );  
39.       }  
40.     }  
41.   }  
42.   return ;  
43. }  
44.   
45. int main(void)  
46. {  
47.   int n;  
48.   while( cin >> n && n ){  
49.   
50.     for(int i=0; i<n; ++i){  
51.       cin >> cost[i];  
52.     }  
53.   
54.     for(int i=0; i<n; ++i){  
55.       for(int j=0; j<n; ++j){  
56.         cin >> g[i][j];  
57.       }  
58.     }  
59.   
60.     wf(n);  
61.       
62.     static int c[N];  
63.     copy( cost, cost + n, c );  
64.       
65.     int mx = 0;  
66.     for(int i=0; i<n; ++i){  
67.       int mn = 1 << 24;  
68.       for(int j=0; j<n; ++j){  
69.         if( i != j ) mn = min(mn, g[i][j]);  
70.       }  
71.       mx = max(mx, mn);  
72.       c[i] += mn;  
73.     }  
74.   
75.     sort( c, c + n );  
76.     lim = 0;  
77.     for(int i=0, sum = -mx; i < n && sum + c[i] <= TIME; lim = ++i){  
78.       sum += c[i];  
79.     }  
80.   
81.     result = 0;  
82.     for(int i=0; i<n; ++i){  
83.       rec(i, (1 << i), cost[i], n, 1);  
84.     }  
85.     cout << result << endl;  
86.   }  
87.   return 0;  
88. }  

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