Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
treasure
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#define N 12
#define INFINITE 999999999
using namespace std;
int p[N][N];
int f[N][1 << N], g[1 << N][1 << N];
int h[1 << N], c;
int main() //treasure.cpp
{
int n, m, u, v, w;
int i, j, k, t, o;
freopen("treasure.in" , "r", stdin );
freopen("treasure.out", "w", stdout);
scanf("%d %d", &n, &m);
for(i = 0;i < N;i ++)
for(j = 0;j < N;j ++)
p[i][j] = i == j ? 0 : INFINITE;
while(m --)
{
scanf("%d %d %d", &u, &v, &w);
u --;
v --;
p[u][v] = min(p[u][v], w);
p[v][u] = min(p[v][u], w);
}
for(i = 1;i < (1 << n);i ++)
{
for(j = i, c = 0;j;j = i & (j - 1))
h[c ++] = j;
for(j = c - 1;j > -1;j --)
{
v = h[j];
for(k = 0;k < n;k ++)
if(v & (1 << k))
break;
for(t = 0, g[i][v] = INFINITE;t < n;t ++)
if(i & ~v & (1 << t))
g[i][v] = min(g[i][v], g[i & ~(1 << k)][v & ~(1 << k)] + p[k][t]);
}
}
for(i = 0;i < N;i ++)
for(j = 0;j < (1 << N);j ++)
f[i][j] = INFINITE;
for(i = 0;i < n;i ++)
f[0][1 << i] = 0;
for(i = 1, o = INFINITE;i < n;i ++)
{
for(j = 0;j < (1 << n);j ++)
for(k = j;k;k = j & (k - 1))
if(g[j][k] != INFINITE)
f[i][j] = min(f[i][j], f[i - 1][j & ~k] + i * g[j][k]);
o = min(o, f[i][(1 << n) - 1]);
}
printf("%d\n", n == 1 ? 0 : o);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.