結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
![]() |
提出日時 | 2021-04-27 19:14:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 5,000 ms |
コード長 | 2,815 bytes |
コンパイル時間 | 3,798 ms |
コンパイル使用メモリ | 199,528 KB |
最終ジャッジ日時 | 2025-01-21 01:26:00 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef vector<ll> vl;typedef pair<ll, ll> pl;typedef priority_queue<ll> pq;typedef priority_queue<ll, vl, greater<>> pqr;struct edge {ll from;ll to;ll cost;edge(ll f, ll t, ll c) : from(f), to(t), cost(c) { }};typedef vector<vector<ll> > Graph;typedef vector<vector<edge> > WGraph;#define rep(i, n) for(int i = 0; i < (int)(n); i++)#define rep3(i, k, n) for(int i = k; i < (int)(n); i++)#define all(v) v.begin(), v.end()#define pb emplace_back#define V vector#define SZ(x) (x).size()#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl#define uniquify(vec) (vec).erase(std::unique((vec).begin(), (vec).end()), (vec).end())constexpr ll MOD1 = 1e9 + 7;constexpr ll MOD9 = 998244353;constexpr ll INF = MOD1*MOD1+1;ll dnum(ll d){return to_string(d).length();}ll power(ll x, ll n){ll ret=1;while(n>0){if(n&1) ret = ret * x;x = x*x;n >>= 1;}return ret;}template<typename T>void rsort(V<T> &v){sort(all(v), greater<T>());}template<typename T, typename S>std::ostream &operator<<(std::ostream& os, const pair<T, S> &p){os << "(" << p.first << ", " << p.second << ")";return os;}template <typename T>std::ostream &operator<<(std::ostream& os, const vector<T> &v){int n = v.size();os << "[";for(int i = 0; i < n; i++){if(i == n - 1) os << v[i];else os << v[i] << ", ";}os << "]";return os;}template <typename T, typename S>std::ostream &operator<<(std::ostream& os, const map<T, S> &mp){for(auto iter = mp.begin(); iter != mp.end(); iter++){os << "(" << iter->first << ", " << iter->second << ")" << " ";}return os;}template <typename T>std::ostream &operator<<(std::ostream& os, const set<T> &s){os << "{";for(auto c : s) os << c << " ";os << "}";return os;}template <typename T>bool chmax(T &a, const T& b) {if (a < b) {a = b; return true;}return false;}template <typename T>bool chmin(T &a, const T& b) {if (a > b) {a = b; return true;}return false;}template <typename T>void fin(const T &a){cout << a << '\n';exit(0);}int main() {cin.tie(nullptr);ios::sync_with_stdio(false);ll n,m; cin >> n >> m;V<V<pl>> list(n);rep(i,m){ll i1, i2, s; cin >> i1 >> i2 >> s;list[i2].pb(i1, s);}vl dp(1<<n, 0);rep(S, 1<<n){rep(i,n){if(S & (1<<i)) continue;ll sc = 0;for(auto p : list[i]){if(S & (1 << p.first)) sc += p.second;}chmax(dp[S|(1<<i)], dp[S] + sc);}}cout << dp[(1<<n)-1] << '\n';return 0;}