# Cod sursa(job #631347)

Utilizator Data 7 noiembrie 2011 20:59:36 Ciclu hamiltonian de cost minim 80 cpp done Arhiva educationala 1.67 kb
``````#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cfloat>
#include <numeric>

using namespace std;

const int    oo  = 0x3f3f3f3f;
const double eps = 1e-9;

typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;

#define sz(c) int ((c).size())
#define all(c) (c).begin(), (c).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define FORIT(i, c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define mp make_pair
#define pb push_back
#define MAX_N 20

int dp[1 << MAX_N][MAX_N];
int cost[MAX_N][MAX_N];
int N, M;

int main () {
freopen ("hamilton.in", "r", stdin);
freopen ("hamilton.out", "w", stdout);

scanf ("%d %d", &N, &M);

memset (cost, oo, sizeof (cost));
FOR (i, 0, M) {
int x, y, c;
scanf ("%d %d %d", &x, &y, &c);

cost[x][y] = c;
}

FOR (i, 0, (1 << N)) FOR (j, 0, N) dp[i][j] = oo;

dp[1][0] = 0;
FOR (i, 1, (1 << N)) FOR (j, 0, N) {
if (dp[i][j] == oo) continue;
FOR (k, 0, N) {
if (((i >> k) & 1) || cost[j][k] == oo) continue;

dp[i|(1 << k)][k] = min(dp[i|(1 << k)][k], dp[i][j] + cost[j][k]);
}
}
int RESULT = dp[(1 << N) - 1][0];
FOR (i, 1, N) RESULT = min (RESULT, dp[(1 << N) - 1][i] + cost[i][0]);

printf ("%d\n", RESULT);

return 0;
}
``````