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;

typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;

#define rep(i,j) for(int i=0;i<(j);i++)
#define reps(i,j,k) for(int i=j;i<=k;i++)
#define in(i,j,k) ((i)>=(j)&&(i)<=(k))
#define INF (1<<28)
#define pb(i) push_back(i)
#define fs first
#define sc second

const char dx[]={0,1,0,-1},dy[]={1,0,-1,0};

bool find(ll source, int n){
	return source & (1ll << n);
}

ll add(ll &source, int n){
	source |= (1ll << n);
	return source;
}

ll erase(ll &source, int n){
	source &= ~(1ll<<n);
	return source;
}

typedef pair<long,long> pll;

int main(){
	int n,m;
	cin >> n >> m;
	vector<int> c(n);
	vector< vector<int> > edge(n);
	vector< vector<ll> > memo(n);
	rep(i,n) cin >> c[i];
	rep(i,m){
		int s,t;
		cin >> s >> t;
		edge[--s].push_back(--t);
		edge[t].push_back(s);
	}
	vector<int> v(n,INF);
	stack<pll> st;//(node,set)
	st.push(pll(0,1));

	while(!st.empty()){
		int node = st.top().fs;
		ll path = st.top().sc;
		st.pop();
		ll tmp = path;
		rep(i,edge[node].size()){
			add(tmp,edge[node][i]);
		}
		bool f = false;
//		cout << node << " : " << memo[node].size() << endl;
//		int hoge = 0;rep(i,n)if(find(tmp,i)){cout<<i<<",";hoge+=c[i];}cout <<"->"<<hoge<<endl;
		rep(i,memo[node].size()){
			if((memo[node][i]&tmp)==memo[node][i]){
				f=true;
				break;
			}
		}
		if(node == n-1) memo[node].push_back(tmp);
		if(f || node == n-1)continue;
		memo[node].push_back(tmp);
		rep(i,edge[node].size()){
			st.push(pll(edge[node][i],tmp));
		}
	}
	int ans = INF;
/*
	rep(i,memo.size()){
		cout << i << endl;
		rep(j,memo[i].size()){
			int tmp = 0;
			rep(k,n)if(find(memo[i][j],k)){
				cout << k << ",";
				tmp += c[k];
			}
			cout << "->" << tmp << endl;
		}
	}
*/
	rep(i,memo[n-1].size()){
		int tmp = 0;
		rep(j,n)if(find(memo[n-1][i],j)){
			tmp += c[j];
//			cout << j << ",";
		}
//		cout << tmp << endl;
		ans = min(tmp,ans);
	}
	cout <<ans<< endl;


	return 0;
}