Pagini recente » Borderou de evaluare (job #2582528) | Cod sursa (job #2831025)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
const int NMAX = 19,
XMAX = (1 << 18),
INF = (1 << 30);
int N, M, NN, Cost[NMAX][NMAX], C[XMAX][NMAX];
vector < int > G[NMAX];
void citire() {
int x, y, i, j;
in >> N >> M;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
Cost[i][j] = INF;
for (i = 1; i <= M; ++i) {
in >> x >> y;
G[y].push_back(x);
in >> Cost[x][y];
}
NN = (1 << N) - 1;
}
void calcul() {
int i, j;
for (int i = 0; i <= NN; ++i)
for (int j = 0; j <= N; ++j)
C[i][j] = INF;
C[1][0] = 0;
for(i = 0; i <= NN; ++i)
for(j = 0; j < N; j++)
if(i & (1 << j))
for (int& x : G[j]) {
if (i & (1 << x))
C[i][j] = min(C[i][j], C[i ^ (1 << j)][x] + Cost[x][j]);
}
}
int main(){
int Sol = INF;
citire();
calcul();
for (int& nod : G[0]) {
Sol = min(Sol, C[NN][nod] + Cost[nod][0]);
}
if (Sol == INF)
out << "Nu exista solutie";
else
out << Sol;
return 0;
}