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:
#pragma GCC optimize "O3"

#include<bits/stdc++.h>

using namespace std;

constexpr int N = 40;

typedef long long LL;

int n, m, c[N], ans = INT_MAX;
LL adj[N], pw2[N];

void dfs(int u, LL ad) {
  if(u == n - 1) {
    ad |= pw2[u];
    LL aad = 0;
    for(int i = 0; i < n; ++i)
      if(ad & pw2[i])
        aad |= adj[i];
    int tans = 0;
    for(int i = 0; i < n; ++i)
      if(aad & pw2[i])
        tans += c[i];
    ans = min(ans, tans);
    return;
  }
  for(int v = 0; v < n; ++v) 
    if((adj[u] & pw2[v]) && !(adj[v] & ad))
      dfs(v, ad | pw2[u]);
}

int main() {

  for(int i = 0; i < N; ++i)
    pw2[i] = (1LL << i);

  scanf("%d %d", &n, &m);
  for(int i = 0; i < n; ++i)
    scanf("%d", c+i);
  for(int i = 0; i < m; ++i) {
    int u, v; scanf("%d %d", &u, &v); --u, --v;
    adj[u] |= pw2[v];
    adj[v] |= pw2[u];
  }

  dfs(0, 0);
  printf("%d\n", ans);

}