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 <cmath>
#include <vector>
#include <iomanip>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <limits> 

using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<PII> VP;
typedef vector<ll> VL;
typedef vector<VL> VVL;

int n, m, sol;
VI C;
VVI g;
VL adj;
ll used;

int Count(ll guarded) {
	int res = 0;
	for (int i = 0; i < n; ++i)
		if (guarded&(1LL << i))
			res += C[i];
	return res;
}

void dfs(int u, int par, ll guarded) {
	if ((adj[u] ^ (1LL << par))&used) return;
	used |= (1LL << u);
	guarded |= adj[u];
	if (u == n-1) {
		sol = min(sol, Count(guarded));
		used ^= (1LL << u);
		return;
	}
	for (auto& v : g[u]) {
		if ((1LL << v)&used) continue;
		dfs(v, u, guarded);
	}
	used ^= (1LL << u);
}

int main() {
	ios::sync_with_stdio(false);
	while (cin >> n >> m) {
		C = VI(n);
		for (auto& x : C) cin >> x;
		g = VVI(n);
		adj = VL(n, 0);
		int u, v;
		for (int i = 0; i < m; ++i) {
			cin >> u >> v;
			--u; --v;
			g[u].push_back(v);
			g[v].push_back(u);
			adj[u] |= (1LL << v);
			adj[v] |= (1LL << u);
		}
		sol = 1 << 30;
		used = 0;
		dfs(0, 52, 0);
		cout << sol << '\n';
	}
}