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;
#define LL long long
int N,M,x,y,pt;
LL b[50];
int C[50];
int st[50],ne[5010],go[5010];
class rec{
	public:
	int x,l;
	LL d;
	bool operator < (const rec &X)const{
		return l<X.l;
	}
	bool operator > (const rec &X)const{
		return l>X.l;
	}
}p1,p2;
class poi{
	public:
	LL d;
	int x;
	bool operator < (const poi &X)const{
		if (x!=X.x)return x<X.x;
		return d<X.d;
	}
};
set <poi> used;
priority_queue <rec ,vector <rec >, greater <rec > > heap;
void Add(int x,int y){ne[++pt]=st[x];st[x]=pt;go[pt]=y;}
int main() {
	scanf("%d%d",&N,&M);
	for (int i=0;i<N;i++)scanf("%d",&C[i]);
	for (int i=1;i<=M;i++){
		scanf("%d%d",&x,&y);
		x--;y--;
		Add(x,y);
		Add(y,x);
		b[x]|=1ll<<y;
		b[y]|=1ll<<x;
	}
	p1.x=0;p1.d=1;p1.l=C[0];
	for (int i=st[0];i;i=ne[i])
		p1.l+=C[go[i]];
	heap.push(p1);
	for (;;){
		p1=heap.top();
		heap.pop();
		if (used.find((poi){p1.d,p1.x})!=used.end())continue;
		if (p1.x==N-1)break;
		used.insert((poi){p1.d,p1.x});
		for (int i=st[p1.x];i;i=ne[i]){
			if ((p1.d>>go[i])&1)continue;
			if (b[go[i]]&(p1.d^(1ll<<p1.x)))continue;
			p2.x=go[i];p2.d=p1.d^(1ll<<go[i]);p2.l=p1.l;
			for (int j=st[p2.x];j;j=ne[j])
				if (!(b[go[j]]&p1.d))
					if (!((p1.d>>go[j])&1))
						p2.l+=C[go[j]];
			if (used.find((poi){p2.d,p2.x})!=used.end())continue;
			heap.push(p2);
		}
	}
	printf("%d\n",p1.l);
    return 0;
}