結果

提出番号 2180
提出者 小林くん
言語 C++
提出日時 2018-10-15 23:08:12
問題名 (70)アルゴリズムのお勉強
結果 CE
点数 0%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 CE 0% 0ms 0KB
2 CE 0% 0ms 0KB
3 CE 0% 0ms 0KB
4 CE 0% 0ms 0KB
5 CE 0% 0ms 0KB
6 CE 0% 0ms 0KB
7 CE 0% 0ms 0KB
8 CE 0% 0ms 0KB
9 CE 0% 0ms 0KB
10 CE 0% 0ms 0KB
11 CE 0% 0ms 0KB
12 CE 0% 0ms 0KB
13 CE 0% 0ms 0KB
14 CE 0% 0ms 0KB
15 CE 0% 0ms 0KB
16 CE 0% 0ms 0KB
17 CE 0% 0ms 0KB
18 CE 0% 0ms 0KB
19 CE 0% 0ms 0KB
20 CE 0% 0ms 0KB
21 CE 0% 0ms 0KB
22 CE 0% 0ms 0KB
23 CE 0% 0ms 0KB
24 CE 0% 0ms 0KB
25 CE 0% 0ms 0KB
26 CE 0% 0ms 0KB
27 CE 0% 0ms 0KB
28 CE 0% 0ms 0KB
29 CE 0% 0ms 0KB
30 CE 0% 0ms 0KB

ソースコード

#include <iostream>
#define max_n 16
int N;
int cost[max_n];
int easy[max_n][max_n];
int dp[1<<max_n][max_n];

int cal(int a,int b){
    
    if (dp[a][b]>=0) {
        return dp[a][b];
    }
    
    if (a==(1<<N)-1&&b==0) {
        return dp[a][b]=0;
    }
    //aは通った道,bは今いる位置
    
    int res=2000000;
    
    for (int i=0; i<N; i++) {
        if (!(a>>i&1)) {
            int d=cost[i];
            
            for (int j=0; j<N; j++) {
                if (a>>j&1) {
                    d-=easy[j][i];
                }
            }
            
            if (res>cal(a|1<<i, i)+d) {
                res=cal(a|1<<i, i)+d;
            }
        }
    }
    
    return dp[a][b]=res;
}

int main() {
    
    scanf("%d",&N);
    
    for (int i=0; i<N; i++) {
        scanf("%d",&cost[i]);
    }
   
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            scanf("%d",&easy[i][j]);
        }
    }
    
    memset(dp, -1, sizeof(dp));
    
    printf("%d",cal(0, 0));
    
return 0;
}