Pagini recente » Cod sursa (job #1676961) | Cod sursa (job #2490688) | Cod sursa (job #1758677) | Cod sursa (job #1770755) | Cod sursa (job #1212034)
#include <fstream>
#include <vector>
#define DIM 18
#define INF 100000000
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
vector< pair<int, int> > L[DIM];
vector< pair<int, int> > K[DIM];
int D[1<<DIM][DIM];
int n, m, c, x, y, i, minim, j;
void rec(int stare, int nod) {
// D[stare][nod] = costul minim sa vizitez toate nodurile din stare
// si ultimul sa fie nod
if (!(stare & (1<<nod)))
return;
if (D[stare][nod]!=INF)
return;
if (stare == 1)
return;
//caut muchie [x nod] si ma intereseaza [stare fara nod][x]
for (int i=0;i<K[nod].size();i++) {
int x = K[nod][i].first;
if (!(stare & (1<<x)))
continue;
rec(stare-(1<<nod), x);
y = D[stare-(1<<nod)][x] + K[nod][i].second;
if (D[stare][nod] > y)
D[stare][nod] = y;
}
}
int main(){
fin>>n>>m;
for (i=1;i<=m;i++) {
fin>>x>>y>>c;
//L[x].push_back( make_pair(y,c) );
K[y].push_back( make_pair(x,c) );
}
for (i=0;i<(1<<n);i++)
for (j=0;j<n;j++)
D[i][j] = INF;
D[1][0] = 0;
minim = INF;
for (i=0;i<K[0].size();i++) {
rec((1<<n)-1, K[0][i].first);
if (minim > D[(1<<n)-1][K[0][i].first] + K[0][i].second)
minim = D[(1<<n)-1][K[0][i].first] + K[0][i].second;
}
if (minim != INF)
fout<<minim;
else
fout<<"Nu exista solutie";
return 0;
}