Cod sursa(job #2923548)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 15 septembrie 2022 17:57:16
Problema Ciclu hamiltonian de cost minim Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
// acest program a fost facut in incinta Colegiului National de Informatica "Tudor Vianu"
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 18;
const int INF = 1e9;

int n, m;
int cost[NMAX + 1][NMAX + 1];
int dp[(1 << NMAX)][NMAX + 1];

int DP(int mask, int v) {
	if(dp[mask][v] != -1) {
		return dp[mask][v];
	}

	dp[mask][v] = INF;

	for(int u = 0; u < n; u++) {
		if(cost[u][v] && (mask & (1 << u))) {
			dp[mask][v] = min(dp[mask][v], DP(mask ^ (1 << v), u) + cost[u][v]);
		}
	}

	return dp[mask][v];
}

int main() {
	ios_base :: sync_with_stdio(0); fin.tie(0); fout.tie(0);
	fin >> n >> m;

	for(int i = 1; i <= m; i++) {
		int u, v, c;
		fin >> u >> v >> c;

		cost[u][v] = c;
	}

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

	int ans = INF;

	for(int i = 0; i < n; i++) {
		if(cost[i][0]) {
			ans = min(ans, DP((1 << n) - 1, i) + cost[i][0]);
		}
	}

	if(ans == INF) {
		fout << "Nu exista solutie!\n";
	} else {
		fout << ans << '\n';
	}

	fin.close();
	fout.close();
	return 0;
}