Cod sursa(job #2294399)

Utilizator ancabdBadiu Anca ancabd Data 2 decembrie 2018 13:06:31
Problema Ciclu hamiltonian de cost minim Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>

using namespace std;

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

#define Inf 0x3f3f3f

vector< vector< pair<int, int> > > G;
vector< vector<int> > c;
vector< pair<int, int> > LastV;

int N, M;

int main()
{
    fin >> N >> M;

    G =  vector< vector< pair<int, int> > >(N);
    c = vector< vector<int> >((1 << N) + 1, vector<int>(N, Inf));

    for (int i = 0, x, y, w; i < M; i ++)
    {
        fin >> x >> y >> w;
        G[x].push_back({y, w});

        if (y == 0)LastV.push_back({x, w});
    }

    // initialization
    //for (int i = 0; i < N; i ++)
      //  c[1 << i][i] = 0;
      c[1][0] = 0;

    int k, w;
    for (int a = 1; a < (1 << N); a ++)
        for (int i = 0; i < N; i ++)
            if (a & (1 << i))
                for (int j = 0; j < G[i].size(); j ++)
                {
                    k = G[i][j].first;
                    w = G[i][j].second;
                    if (!(a & (1 << k)))
                        c[a + (1 << k)][k] = min(c[a + (1 << k)][k], c[a][i] + w);
                }
    int Rez = Inf;
    for (int i = 0; i < LastV.size(); i ++)
    {
        k = LastV[i].first;
        w = LastV[i].second;
        Rez = min(Rez, c[(1 << N) - 1][k] + w);
    }
    if (Rez == Inf)fout << "Nu exista solutie";
    else fout << Rez;
    return 0;
}