# Cod sursa(job #1976438)

Utilizator Data 3 mai 2017 14:01:52 Ciclu hamiltonian de cost minim 100 cpp done Arhiva educationala 1.34 kb
``````#include <fstream>
#include <vector>

using namespace std;

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

const int inf = 1e9;
vector<int> g[20];
int d[1 << 18][20], cost[20][20];

int main()
{
int n, m, x, y, c;
in >> n >> m;
for(int i = 1; i <= m; ++i)
{
in >> x >> y >> c;
cost[x][y] = c;
g[x].push_back(y);
}

int lim = 1 << n;
for(int mask = 0; mask < lim; ++mask)
{
for(int i = 0; i < n; ++i)
{
d[mask][i] = inf;
}
}
d[1][0] = 0;
for(int mask = 1; mask < lim; ++mask)
{
for(int i = 0; i < n; ++i)
{
if(mask & (1 << i))
{
for(vector<int> :: iterator it = g[i].begin(); it != g[i].end(); ++it)
{
if((mask & (1 << *it)) == 0)
{
d[mask | (1 << *it)][*it] = min(d[mask | (1 << *it)][*it], d[mask][i] + cost [i][*it]);
}
}
}
}
}
int sol = inf;
for(int i = 0; i < n; ++i)
{
if(cost[i][0])
{
sol = min(sol, d[lim - 1][i] + cost[i][0]);
}
}
if(sol == inf)
out << "Nu exista solutie";
else
out << sol;

return 0;
}
``````