Cod sursa(job #2169514)

Utilizator SenibelanMales Sebastian Senibelan Data 14 martie 2018 15:53:14
Problema Ciclu hamiltonian de cost minim Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream in("hamilton.in");
ofstream out("hamilton.out");

const int oo = 1000000000;
const int NMAX = 20;
int N, M;
vector <int> G[NMAX];
int Cost[NMAX][NMAX];
int DP[1 << NMAX][NMAX];

void Read(){
    in >> N >> M;
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
            Cost[i][j] = oo;
    for(int i = 1; i <= M; ++i){
        int a, b, c;
        in >> a >> b >> c;
        G[b].push_back(a);
        Cost[a][b] = c;
    }
    for(int i = 0; i < 1 << N; ++i)
        for(int j = 0; j < N; ++j)
            DP[i][j] = oo;
}

void Solve(){
    DP[1][0] = 0;
    for(int i = 0; i < 1 << N; ++i){
        for(int j = 0; j < N; ++j){
            if(i & (1 << j)){
                for(int k = 0; k < G[j].size(); ++k){
                    int neighbour = G[j][k];
                    if(i & (1 << neighbour)){
                        DP[i][j] = min(DP[i][j], DP[i ^ (1 << j)][neighbour] + Cost[neighbour][j]);
                    }
                }
            }
        }
    }
}

void Print(){
    int sol = oo;
    for(int i = 0; i < G[0].size(); ++i)
        sol = min(sol, DP[(1 << N) - 1][G[0][i]] + Cost[G[0][i]][0]);
    if(sol == oo)
        out << "-1\n";
    else
        out << sol << "\n";
}


int main(){
    Read();
    Solve();
    Print();
    return 0;
}