結果

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

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 WA 0% 2ms 8384KB
2 WA 0% 2ms 8320KB
3 WA 0% 2ms 8448KB
4 WA 0% 2ms 8208KB
5 WA 0% 2ms 8320KB
6 WA 0% 2ms 7888KB
7 WA 0% 1ms 7792KB
8 WA 0% 2ms 8416KB
9 WA 0% 2ms 7600KB
10 WA 0% 2ms 8064KB
11 WA 0% 1ms 8496KB
12 WA 0% 2ms 7488KB
13 WA 0% 2ms 7888KB
14 WA 0% 2ms 8608KB
15 WA 0% 2ms 8208KB
16 WA 0% 2ms 8448KB
17 WA 0% 2ms 7600KB
18 WA 0% 2ms 7232KB
19 WA 0% 2ms 8048KB
20 WA 0% 2ms 8512KB
21 WA 0% 1ms 8688KB
22 WA 0% 2ms 7904KB
23 WA 0% 2ms 8432KB
24 WA 0% 1ms 7888KB
25 WA 0% 2ms 8288KB
26 WA 0% 2ms 8224KB
27 WA 0% 2ms 7536KB
28 WA 0% 2ms 7600KB
29 WA 0% 2ms 8432KB
30 WA 0% 2ms 7504KB

ソースコード

#include <stdio.h>
#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]);
        }
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            dp[i][j]=-1;
        }
    }
    
    printf("%d",cal(0, 0));
    
return 0;
}