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;
bitset<N> adj[N];

void dfs(int u, bitset<N> &ad) {
  if(u == n - 1) {
    ad[u] = true;
    bitset<N> aad;
    for(int i = 0; i < n; ++i)
      if(ad[i])
        aad |= adj[i];
    int tans = 0;
    for(int i = 0; i < n; ++i)
      if(aad[i])
        tans += c[i];
    ans = min(ans, tans);
    ad[u] = false;
    return;
  }
  for(int v = 0; v < n; ++v) 
    if(adj[u][v] && (adj[v] & ad).none()) {
      ad[u] = true;
      dfs(v, ad);
      ad[u] = false;
    }
}

int main() {

  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][v] = adj[v][u] = true;
  }
  bitset<N> ad;
  dfs(0, ad);
  printf("%d\n", ans);

}