Problem: Example

Input

6 6
3
1
9
4
3
6
1 2
1 4
2 6
5 4
6 5
3 2


Output

17

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

const int maxn = 40;
uint64_t adj[maxn];
int n, m, c[maxn], sum[2][1 << 20];

int Eval(uint64_t mask) {
    return sum[0][mask & ((1LL << (n / 2)) - 1)] + sum[1][mask >> (n / 2)];
}

int dfs(int x, uint64_t ng, uint64_t f) {
    if (x == n - 1) return Eval(ng);
    uint64_t cand = (adj[x] & ~f);
    int res = 1E9;
    while (cand > 0) {
        int u = __builtin_ctzll(cand & -cand);
        if (u != x)
            res = min(res, dfs(u, ng | adj[x] | adj[u], (adj[x] ^ (1ULL << u)) | f));
        cand -= (1ULL << u);
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", &c[i]);
    for (int i = 0; i < n; ++i) adj[i] |= (1ULL << i);
    for (int i = 0; i < m; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        --u, --v;
        adj[u] |= (1ULL << v);
        adj[v] |= (1ULL << u);
    }
    for (int i = 0; i < (1 << (n / 2)); ++i) {
        for (int j = 0; j < n / 2; ++j) {
            if (i >> j & 1)
                sum[0][i] += c[j];
        }
    }
    for (int i = 0; i < (1 << (n - n / 2)); ++i) {
        for (int j = 0; j < n - n / 2; ++j) {
            if (i >> j & 1)
                sum[1][i] += c[j + n / 2];
        }
    }
    printf("%d\n", dfs(0, 0LL, 0LL));
}