Submission #75973134

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define all(x) (x).begin(), (x).end()
#define pb push_back

template<class T> inline bool chmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chmin(T& a, T b) { return a > b ? a = b, 1 : 0; }

const int MOD = 1e9 + 7;

void solve() {
    
    int n,m;cin>>n>>m;
    ll base=0;
    vector<vector<ll>> dist(n+1,vector<ll>(n+1,1e18));
    vector<int> deg(n+1,0);
    for(int i=0;i<=n;i++){
        dist[i][i]=0;
    }
    for(int i=0;i<m;i++){
        ll u,v,w;cin>>u>>v>>w;
        deg[v]++;
        deg[u]++;
        base+=w;
        chmin(dist[u][v],w);
        chmin(dist[v][u],w);
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dist[i][k]!=1e18&&dist[k][j]!=1e18)  {
                    chmin(dist[i][j],dist[i][k]+dist[k][j]);
                }
            }
        }
    }
    vector<int> odd;
    for(int i=1;i<=n;i++){
        if(deg[i]&1)odd.push_back(i);   
    }
    if(odd.size()==0){
        cout<<base<<'\n';
        return;
    }
    int k=odd.size();
    vector<ll> dp(1<<k,1e18);
    dp[0]=0;
    for(int mask=0;mask<(1<<k);mask++){
        if(dp[mask]==1e18)continue;

        int i=0;
        for(;i<k;i++){
            if(!(mask&(1<<i)))break;
        }
        for(int j=i+1;j<k;j++){
            if(!(mask&(1<<j))){
                int nxt=mask|(1<<i)|(1<<j);

                ll cost=dist[odd[i]][odd[j]];
                chmin(dp[nxt],dp[mask]+cost);
            }
        }
    }
    cout<<base+dp[(1<<k)-1]<<'\n';

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tt = 1;
    //cin >> tt;

    while (tt--) {
        solve();
    }

    return 0;
}

Submission Info

Judge Result