Skip to content

Instantly share code, notes, and snippets.

@andrei512
Last active January 18, 2017 09:28
Show Gist options
  • Save andrei512/e3b489a288bf6817c06229e1e2cb6399 to your computer and use it in GitHub Desktop.
Save andrei512/e3b489a288bf6817c06229e1e2cb6399 to your computer and use it in GitHub Desktop.
#include <stdio.h>
#define NNodes 22
int Sum, Min, x, y, n, m, c, f[NNodes], st[NNodes], a[NNodes][NNodes];
void back(int k) {
if(k == n + 1) {
if(a[st[n]][st[1]] > 0) {
Sum += a[st[n]][st[1]];
if(Sum < Min)
Min = Sum;
Sum -= a[st[n]][st[1]];
}
return ;
}
for(int i = 0; i < n ; ++i) {
if(f[i] == 0){
st[k] = i;
if(a[st[k - 1]][st[k]] > 0){
Sum = Sum + a[st[k - 1]][st[k]];
f[i] = 1;
back(k + 1);
f[i] = 0;
Sum = Sum - a[st[k - 1]][st[k]];
}
}
}
}
int main() {
freopen("hamilton.in", "r", stdin);
freopen("hamilton.out", "w", stdout);
scanf("%d%d", &n, &m);
int i;
for(i = 1; i <= m ; ++i) {
scanf("%d%d", &x, &y);
scanf("%d", &c);
a[x][y] = c;
}
Min = 2000000000;
for(i = 0; i < n ; ++i){
st[1] = i;
f[i] = 1;
Sum = 0;
back(2);
f[i] = 0;
}
printf("%d", Min);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment