提出 #73993530

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int inf = 1e18;

void solve(){
    
    int n, m; cin >> n >> m;

    vector<vector<int>> graph(n);
    vector<vector<int>> dist(n, vector<int>(n, inf));

    for(int i = 0; i < n; i++) dist[i][i] = 0;

    for(int i = 0; i < m; i++){
        int u, v, w; 
        cin >> u >> v >> w;
        u--; v--;

        graph[u].push_back(v);
        graph[v].push_back(u);

        dist[u][v] = min(dist[u][v], w);
        dist[v][u] = min(dist[v][u], w);
    }

    // Floyd Warshall
    for(int k = 0; k < n; k++){
        for(int u = 0; u < n; u++){
            for(int v = 0; v < n; v++){
                dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v]);
            }
        }
    }

    vector<int> vis(n, 0);

    auto dfs = [&](int u, auto &&self)->void{
        vis[u] = 1;
        for(auto &v : graph[u]){
            if(!vis[v]) self(v,self);
        }
    };

    dfs(0, dfs);

    for(int i = 0; i < n; i++){
        if(!vis[i]){
            cout << -1 << endl;
            return;
        }
    }

    vector<vector<int>> dp(1LL<<n, vector<int>(n, inf));

    dp[1][0] = 0;

    for(int mask = 0; mask < (1LL<<n); mask++){

        for(int u = 0; u < n; u++){

            if(dp[mask][u] == inf) continue;

            for(int v = 0; v < n; v++){

                int newMask = mask;

                if(!(mask & (1<<v))){
                    newMask |= (1<<v);
                }

                dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }

    int ans = inf;
    int full = (1LL<<n) - 1;

    for(int u = 0; u < n; u++){

        if(dp[full][u] == inf) continue;

        ans = min(ans, dp[full][u] + dist[u][0]);
    }

    cout << ans << endl;
}

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
}

提出情報

ジャッジ結果