D. Traveling Graph, C++ (gcc)

D. Traveling Graph

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

const ll inf = (ll)1e18;

ll g[16][16], dis[16][16], n;

void Floydd(){
    for(int j = 1; j <= n; j++)
        for(int k = 1; k <= n; k++)
            dis[j][k] = g[j][k];
        
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= n; k++)
                if(dis[j][k] > dis[j][i] + dis[i][k]) dis[j][k] = dis[j][i] + dis[i][k];
    }
}

void print(){
    for(int j = 1; j <= n; j++){
        for(int k = 1; k <= n; k++)
            cout << dis[j][k] << " ";
        cout << endl;
    }
}

ll dp[16][40001];

ll foo(int from, int mask){
    if(mask == ((1 << (n+1)) - 2)) return dis[from][1];
    if(dp[from][mask] != inf) return dp[from][mask];
    ll &ans = dp[from][mask];
    ans = inf - 1;
    
    for(int j = 1; j <= n; j++){
        if(mask & (1 << j) || g[from][j] == inf) continue;
        ans = min(ans, g[from][j] + foo(j, mask|(1 << j))); 
    }
    return ans;
}

int main(){
    for(int j = 0; j < 16; j++)
        for(int k = 0; k < 40001; k++)
            dp[j][k] = inf;
    
    int m;
    cin >> n >> m;
    for(int j = 0; j < 16; j++)
        for(int k = 0; k < 16; k++)
            g[j][k] = inf;
   
    while(m--){
        ll u, v, w;
        cin >> u >> v >> w;
        g[u][v] = min(g[u][v], w);
        g[v][u] = min(g[v][u], w);
    }
    Floydd();
    //print();
    //cout << ((1 << (n+1)) - 2) << endl;
    
    cout << foo(1, 2) << endl;
    return 0;
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development