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;
int answer = 1e9;
int c[40];
vector<int> g[40];
int n,m;

void dfs(int x,long long bit,int cost){
	long long before = bit;
	// self
	if( !(bit >> x&1) ){
		cost += c[x];
		bit |= (1ll<<x);
	}
	// other
	for( auto i : g[x] ){
		if( !(bit >> i & 1) ){
			bit |= (1ll<<i);
			cost += c[i];
		}
	}
	// branch-cut
	if( cost >= answer ) return;
	if( x == n - 1 ){
		answer = cost;
		return;
	}

	for( auto i : g[x] ){
		if( (before >> i & 1) == 0 ) dfs(i,bit,cost);
	}
}

int main(){
	cin >> n >> m;
	for(int i = 0 ; i < n ; i++){
		cin >> c[i];
	}
	for(int i = 0 ; i < m ; i++){
		int a,b;
		cin >> a >> b;
		--a,--b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(0,0,0);
	cout << answer << endl;


}