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>
#define PIB pair<int,bool>
#define PIL pair<int,long long>
#define MP make_pair
#define X first
#define Y second
using namespace std;
const int maxn=44;
long long e[maxn]; int v[maxn],n,m;
void init(){
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;++i) scanf("%d",v+i);
    for (int i=1,a,b;i<=m;++i) scanf("%d%d",&a,&b),--a,--b,e[a]+=1LL<<b,e[b]+=1LL<<a;
}
void print(long long x){
	if (!x) return; print(x/2); putchar((x&1)+'0');
}
map<PIL,PIB>mp;
void spfa(){
	int ans=~0u>>1;
	static const int maxN=10000011;
    static PIL q[maxN]; int t=0,w=1; q[1]=MP(0,1); mp[q[1]]=MP(v[1],1);
    while (t!=w){
        if (++t==maxN) t=1; mp[q[t]].Y=0;
        if (q[t].X==n-1){
            long long s=q[t].Y|e[n-1]; int V=0;
            for (int i=0;i<n;++i) if ((s>>i)&1) V+=v[i];
            if (V<ans) ans=V;
        }else{
			for (int i=0;i<n;++i) if (!((q[t].Y>>i)&1) && ((e[q[t].X]>>i)&1)){
				PIL nw=MP(i,q[t].Y|e[q[t].X]); int V=0;
				for (int j=0;j<n;++j) if ((nw.Y>>j)&1) V+=v[j];
				map<PIL,PIB>::iterator son=mp.find(nw);
				if (son==mp.end()) mp[nw]=MP(V,0),son=mp.find(nw);
				else if (son->Y.X>V) son->Y.X=V; else continue;
				if (!son->Y.Y){
					son->Y.Y=1; if (++w==maxN) w=1; q[w]=nw; //cout<<nw.X<<' '; print(nw.Y); putchar('\n');
				}
			}
		}
    }
	printf("%d\n",ans);
}
void work(){
    spfa();
}
int main(){
    init();
    work();
    return 0;
}