Cod sursa(job #381349)

Utilizator Data 10 ianuarie 2010 13:53:42 Ciclu hamiltonian de cost minim 100 cpp done Arhiva educationala 1.27 kb
``````#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 20;
const int MAXX = 262150;
const int INF = 1000000000;

int N, M, Sol;
vector <int> A[MAXN];
int C[MAXX][MAXN];
int Cost[MAXN][MAXN];

int calc(int conf, int last)
{
if (C[conf][last] == -1)
{
C[conf][last] = INF;

for (size_t i = 0; i < A[last].size(); ++i) // parcurg nodurile care arata spre ultimul nod din lant
if (conf & (1 << A[last][i]))  // le aleg doar pe cele care apartin lantului
{
if (A[last][i] == 0 && conf != (1<<(last)) + 1) continue; // nodul 1 trebuie sa il scot ultimul

C[conf][last] = min(C[conf][last], calc(conf ^ (1<<last), A[last][i]) + Cost[A[last][i]][last]);
}
}

return C[conf][last];
}

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

Sol = INF;

fin >> N >> M;

for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j) Cost[i][j] = INF;

for (int i = 1; i <= M; ++i)
{
int x, y;

fin >> x >> y;
A[y].push_back(x); // retin arcul invers
fin >> Cost[x][y];
}

memset(C, -1, sizeof(C));
C[1][0] = 0;

for (size_t i = 0; i < A[0].size(); ++i)
Sol = min(Sol, calc((1<<N)-1, A[0][i]) + Cost[A[0][i]][0]);

if (Sol == INF) fout << "Nu exista solutie" << endl;
else fout << Sol << endl;

return 0;
}
``````