# Cod sursa(job #2490009)

Utilizator Data 9 noiembrie 2019 16:05:20 Ciclu hamiltonian de cost minim 100 cpp-64 done Arhiva educationala 2.15 kb
``````#include <bits/stdc++.h>
#define NMAX 18
#define infinity 1000000000
using namespace std;

ifstream fin{"hamilton.in"};
ofstream fout{"hamilton.out"};

int N, M, startNode = 0;

vector<vector<int>> dp(NMAX, vector<int>(1 << NMAX, infinity));
vector<vector<int>> cost(NMAX, vector<int>(NMAX, infinity));
vector<vector<int>> subset(NMAX + 1, vector<int>());

int onBitsCount(int number)
{

while(number)
{
number >>= 1;
}

}

inline bool isBitOn(int position, int number)
{
return (1 << position) & number;
}

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

for(int i = 0; i < (1 << N); ++i)
subset[onBitsCount(i)].push_back(i);

for(int i = 1; i <= M; ++i)
{
int x, y, c;
fin >> x >> y >> c;
cost[x][y] = c;
}

for(int i = 0; i < N; ++i)
{
if(i == startNode) continue;
dp[i][1 << startNode | 1 << i] = cost[startNode][i];
}

for(int lungime_drum = 3; lungime_drum <= N; ++lungime_drum)
{
for(auto& state : subset[lungime_drum])
{
if(isBitOn(startNode, state) == false) continue;

for(int next = 0; next < N; ++next)
{
if(next == startNode || isBitOn(next, state) == false) continue;

int previous_state = state ^ (1 << next);
int minDist = infinity;

for(int node = 0; node < N; ++node)
{
if(node == startNode || node == next || isBitOn(node, state) == false) continue;

minDist = min(minDist, cost[node][next] + dp[node][previous_state]);
}

dp[next][state] = minDist;
}
}
}

int END_STATE = (1 << N) - 1;
int minTour = infinity;

for(int node = 0; node < N; ++node)
{
if(node == startNode) continue;

minTour = min(minTour, dp[node][END_STATE] + cost[node][startNode]);
}

if(minTour == infinity)
fout << "Nu exista solutie";
else
fout << minTour;
}
``````