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 <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cctype>
using namespace std;
typedef long long LL;
const int N = 2005;

int n, m;
int first[55], tot;

struct Edge {
    int y, nex;
}edge[100000];

void addedge(int x, int y) {
    edge[tot] = (Edge) {y, first[x]};
    first[x] = tot++;
}

int val[100];

LL mask1[100];
int bo[55];

LL getMask(int x) {
    LL ans = mask1[x];
    bo[x]++;
    if (x == n - 1) return ans;
    for (int k = first[x]; k != -1; k = edge[k].nex) {
        int y = edge[k].y;
        if (bo[y]) continue;
        LL q = getMask(y);
        if (q != -1) {
            return ans | q;
        }
    }
    return -1;
}

int ans = 0;

int getVal(LL x) {
    int res = 0;
    for (int i = 0; i < n; ++i)
        if (x >> i & 1) res += val[i];
    return res;
}

int vis[100];

int DFS(int x) {
    if (x == n - 1) return 1;
    if (vis[x]) return 0;
    vis[x] = 1;
    for (int k = first[x]; k != -1; k = edge[k].nex)
        if (DFS(edge[k].y)) return 1;
    return 0;
}

void dfs(int x, LL mask, int res, int dep) {
    if (res >= ans) return ;
    if (x == n - 1) {
        ans = min(ans, res);
        return ;
    }
    memcpy(vis, bo, sizeof(int) * n);
    vis[x] = 0;
    if (!DFS(x)) return ;
    for (int k = first[x]; k != -1; k = edge[k].nex) {
        int y = edge[k].y;
        //if (bo[y]) continue;
        ++bo[y];
        if (bo[y] > 1) continue;
        dfs(y, mask1[y] | mask, getVal(mask1[y] | mask), dep + 1);
        //bo[y] = 1;
    }
    for (int k = first[x]; k != -1; k = edge[k].nex) {
        int y = edge[k].y;
        --bo[y];
    }
}

int main() {
    srand(time(0));
    //freopen("1", "r", stdin);
    scanf("%d%d", &n, &m);
    // n = 40, m = 1000;
    //freopen("out.txt", "w", stdout);
    //printf("%d %d\n", n, m);
    memset(first, -1, sizeof(first));
    for (int i = 0; i < n; ++i) {
        scanf("%d", &val[i]);        
        //  val[i] = rand() % 100 + 1;
        //printf("%d\n", val[i]);
        mask1[i] = 1LL << i;
    }
    tot = 0;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        //x = rand() % n + 1;
        //y = rand() % n + 1;
        //printf("%d %d\n", x, y);
        --x;
        --y;
        addedge(x, y);
        addedge(y, x);
        mask1[x] |= 1LL << y;
        mask1[y] |= 1LL << x;
    }
    memset(bo, 0, sizeof(bo));
    ans = 1 << 30;
    bo[0] = 1;
    dfs(0, mask1[0], getVal(mask1[0]), 1);
    cout << ans << endl;
    return 0;
}