Pagini recente » Cod sursa (job #717577) | Rating Petric Maria (petric_maria) | Cod sursa (job #1487911) | Cod sursa (job #2462792) | Cod sursa (job #1842105)
#include<bits/stdc++.h>
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
const int INF = 0x3f3f3f3f;
int a[18][18];
int d[18][(1<<18)];
int n,m;
int main(){
in>>n>>m;
for(int i=1;i<=m;i++){
int x,y,c;
in>>x>>y>>c;
a[x][y]=c;
}
int ans = INF;
for(int j=0;j<n;j++){
for(int k=0;k<n;k++)
for(int i=0;i<(1<<n);i++)
d[k][i]=INF;
d[j][(1<<j)]=0;
for(int i=0;i<(1<<n);i++){
for(int e=0;e<n;e++) if(e!=j && i&(1<<e)){
for(int f=0;f<n;f++) if(f!=e && i&(1<<f) && a[f][e]!=0){
d[e][i] = min(d[e][i], d[f][i^(1<<e)] + a[f][e] );
}
}
}
for(int i=0;i<n;i++) if(a[i][j]){
ans = min(ans, d[i][(1<<n)-1] + a[i][j] );
}
}
if(ans == INF) out<<"Nu exista solutie\n";
else out<<ans<<'\n';
return 0;
}