Pagini recente » Cod sursa (job #1305737) | Cod sursa (job #2037686) | Cod sursa (job #2502606) | Cod sursa (job #1856126) | Cod sursa (job #3204351)
// Incercare fara for-ul care selecteaza ca nod initial fiecare nod.
// 70 p
#include <cstring>
#include <fstream>
#include <vector>
using namespace std;
const int MAXN = 20;
const int MAXX = 262150;
const int INF = 100000000;
int N, M, Sol;
vector<int> A[MAXN];
int Cost[MAXN][MAXN];
int C[MAXX][MAXN];
int calc(int start, int conf, int last) {
if (C[conf][last] == -1) { // trebuie calculat
C[conf][last] = INF; // initializam un minim
for (int nod : A[last]) {
if (conf & (1 << nod)) { // nod se afla in configuratie
if (nod == start && ((conf ^ (1 << last)) != (1 << start)))
continue;
C[conf][last] = min(C[conf][last], calc(start, conf ^ (1 << last), nod) + Cost[nod][last]);
}
}
}
return C[conf][last];
}
int main() {
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
fin >> N >> M;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
Cost[i][j] = INF;
for (int i = 1; i <= M; ++i) {
int x, y, c;
fin >> x >> y >> c;
A[y].push_back(x); // arcul invers
Cost[x][y] = c;
}
Sol = INF;
memset(C, -1, sizeof(C));
C[1 << 0][0] = 0;
for (size_t j = 0; j < A[0].size(); ++j)
Sol = min(Sol, calc(0, (1 << N) - 1, A[0][j]) + Cost[A[0][j]][i]);
if (Sol != INF)
fout << Sol << endl;
else
fout << "Nu exista solutie" << endl;
return 0;
}