Submission #00042

ソースコード

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define vi vector<int>
#define all(v2) v2.begin(),v2.end()
#define fi first
#define se second
#define P pair<int,int>
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
 
int mod=1e9+7;
int inf=INT_MAX;
 
 
//cout<<fixed<<setprecision(5);
int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
 
    int n; cin>>n;
 
    vector<vector<ll>> a(n,vector<ll>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }
 
    vector<ll> dp((1<<n),1e18);
    dp[0]=0;
    for(int bit=0;bit<(1<<n);bit++){
        for(int i=0;i<n;i++){
            if(!(bit&(1<<i))){
                dp[bit+(1<<i)]=min(dp[bit+(1<<i)],dp[bit]+a[i][__builtin_popcount(bit)]);
            }
        }
    }
 
    cout<<dp[(1<<n)-1]<<"\n";
 
    return 0;
}

ステータス

項目	データ
問題	0004 - 発表会
ユーザー名	ei2005
投稿日時	2022-05-24 17:53:10
言語	C++17
状態	Accepted
得点	1
ソースコード長	900 Byte
最大実行時間	216 ms
最大メモリ使用量	8912 KB

セット

	セット	得点	Cases
1	ALL	1 / 1	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
case01.in	AC	148 ms	8796 KB	1
case02.in	AC	152 ms	8872 KB	1
case03.in	AC	143 ms	8820 KB	1
case04.in	AC	141 ms	8760 KB	1
case05.in	AC	144 ms	8704 KB	1
case06.in	AC	139 ms	8772 KB	1
case07.in	AC	147 ms	8840 KB	1
case08.in	AC	150 ms	8784 KB	1
case09.in	AC	148 ms	8856 KB	1
case10.in	AC	164 ms	8796 KB	1
case11.in	AC	154 ms	8740 KB	1
case12.in	AC	145 ms	8808 KB	1
case13.in	AC	157 ms	8756 KB	1
case14.in	AC	145 ms	8824 KB	1
case15.in	AC	150 ms	8896 KB	1
case16.in	AC	143 ms	8836 KB	1
case17.in	AC	145 ms	8912 KB	1
case18.in	AC	163 ms	8852 KB	1
case19.in	AC	140 ms	8788 KB	1
case20.in	AC	216 ms	8860 KB	1
sample01.in	AC	21 ms	732 KB	1
sample02.in	AC	20 ms	684 KB	1