Submission #66200

ソースコード

#pragma GCC optimize("O3")
#include <bits/extc++.h>
 
using namespace std;
  
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) begin(x), end(x)
#define Fixed fixed << setprecision(12)
#define int int_fast64_t
using pii = pair<int,int>;
constexpr int32_t INF  = 0x3f3f3f3f;
constexpr int_fast64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9+7;
constexpr int mod2 = 998244353;
  
template <class Func>
class FixPoint : Func {
public:
    explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {}
  
    template <class... Args>
    constexpr decltype(auto) operator()(Args&&... args) const {
        return Func::operator()(*this, std::forward<Args>(args)...);
    }
};
  
template <class Func>
static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept {
    return FixPoint<Func>{forward<Func>(f)};
}
  
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
  
template <class T> using max_heap = priority_queue<T>;
template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class A, class B> using umap = unordered_map<A,B>;
  
template <class T> using Max_Heap = __gnu_pbds::priority_queue<T, less<T>, __gnu_pbds::rc_binomial_heap_tag>;
template <class T> using Min_Heap = __gnu_pbds::priority_queue<T, greater<T>, __gnu_pbds::rc_binomial_heap_tag>;
template <class T> using Set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template <class K, class V> using Umap = __gnu_pbds::gp_hash_table<K, V>;
using Trie = __gnu_pbds::trie<string, __gnu_pbds::null_type, __gnu_pbds::trie_string_access_traits<>, __gnu_pbds::pat_trie_tag, __gnu_pbds::trie_prefix_search_node_update>;
 
template <class T> inline void bye(T x) { cout << x << '\n', exit(0); }
  
inline int square(int a){ return a * a;}
inline int updiv(int a,int b){ return (a + b - 1) / b; }
 
constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
constexpr int dy[] = {0,-1,0,1,1,-1,-1,1};
 
 
signed main(void){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout.setf(ios_base::fixed);
    cout.precision(10);
 
    int n;
    cin >> n;
 
    vector<vector<int> > a(n, vector<int>(n + 1, LINF));
 
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cin >> a[i][j];
        }
    }
 
    vector<int> dp(1 << n, LINF);
    min_heap<pair<int, int> > que;
    dp[0] = 0;
    que.emplace(0, 0);
 
    while(!que.empty()){
        auto [cs, bit] = que.top();
        que.pop();
        if(dp[bit] < cs) continue;
        for(int i = 0; i < n; ++i){
            if(chmin(dp[bit | 1 << i], dp[bit] + a[i][__builtin_popcount(bit)])){
                que.emplace(dp[bit | 1 << i], bit | 1 << i);
            }
        }
    }
 
    cout << dp.back() << '\n';
 
    return 0;
}

ステータス

項目	データ
問題	1108 - 発表会
ユーザー名	ei1903
投稿日時	2021-04-22 17:29:55
言語	C++17
状態	Accepted
得点	1
ソースコード長	3071 Byte
最大実行時間	711 ms
最大メモリ使用量	42284 KB

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
case01.in	AC	665 ms	26820 KB	1
case02.in	AC	606 ms	25668 KB	1
case03.in	AC	707 ms	42284 KB	1
case04.in	AC	612 ms	25616 KB	1
case05.in	AC	656 ms	25536 KB	1
case06.in	AC	693 ms	26088 KB	1
case07.in	AC	617 ms	26512 KB	1
case08.in	AC	607 ms	26376 KB	1
case09.in	AC	686 ms	27084 KB	1
case10.in	AC	681 ms	26416 KB	1
case11.in	AC	711 ms	41864 KB	1
case12.in	AC	677 ms	26900 KB	1
case13.in	AC	624 ms	25696 KB	1
case14.in	AC	611 ms	25420 KB	1
case15.in	AC	598 ms	27108 KB	1
case16.in	AC	614 ms	25696 KB	1
case17.in	AC	631 ms	25372 KB	1
case18.in	AC	634 ms	25724 KB	1
case19.in	AC	594 ms	25420 KB	1
case20.in	AC	615 ms	25448 KB	1
sample01.in	AC	16 ms	616 KB	1
sample02.in	AC	17 ms	576 KB	1