Submission #44949890

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}

void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<ll>> e(n, vector<ll>(n, -1));
    for (int i = 0, a, b, c; i < m; i++)
    {
        cin >> a >> b >> c;
        --a, --b;
        e[a][b] = c;
        e[b][a] = c;
    }
    ll constexpr inf = 1e16;
    vector<vector<ll>> d(1 << n, vector<ll>(n, -inf));
    for (int i = 0; i < n; i++)
    {
        d[1 << i][i] = 0;
    }
    ll ans = 0;
    for (int b = 0; b < (1 << n); b++)
    {
        for (int i = 0; i < n; i++)
        {
            chmax(ans, d[b][i]);
            if(((b >> i) & 1) == 0) continue;
            for (int j = 0; j < n; j++)
            {
                if(e[i][j] == -1) continue;
                if((b >> j) & 1) continue;
                chmax(d[b | (1 << j)][j], d[b][i] + e[i][j]);
            }
            
        }
        
    }
    cout << ans << endl;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    solve();
}

Submission Info

Judge Result