Cod sursa(job #2387904)

Utilizator VadimCCurca Vadim VadimC Data 25 martie 2019 13:38:42
Problema Ciclu hamiltonian de cost minim Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

#define N 20
#define Nr (1 << 18) + 5

#define For(i, a, b) for((i) = (a); (i) < (b); (i)++)

const unsigned int inf = (1 << 30) - 1;

int n, m;
vector<int> G[N];
int cst[N][N];

int c[Nr][N];
int sol;

void init();
void rezolvare();
int cost(int, int);

int main(){
	init();
	rezolvare();
}

void init(){
	int i, j;
	int x, y;
	fin >> n >> m;
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			cst[i][j] = inf;
	For(i, 0, m){
		fin >> x >> y;
		fin >> cst[x][y];
		G[y].push_back(x);
	}
	memset(c, -1, sizeof(c));
	c[1][0] = 0;
}

void rezolvare(){
	int i, j;
	
	sol = inf;
	For(i, 0, G[0].size())
		sol = min(sol, cost((1 << n) - 1, G[0][i]) + cst[G[0][i]][0]);
	
	fout << sol;
}

int cost(int conf, int last){
	if(c[conf][last] == -1){
		int i, v;
		c[conf][last] = inf;
		For(i, 0, G[last].size()){
			v = G[last][i];
			if(conf & (1 << v)){
				if(v == 0 && conf != (1 << last) + 1) continue;
				c[conf][last] = min(c[conf][last], cost(conf ^ (1 << last), v) + cst[v][last]);
			}
		}
	}
	return c[conf][last];
}