結果

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

---

テストケース

ソースコード

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