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 N 41
typedef long long ll;
const int inf=0x3f3f3f3f;
ll adj[N];
int a[N],que[N];
vector<int> g[N];
int n,m,ans,cnt=0,kk=0;
unordered_set<ll> se;
bool bfs(int beg,ll s)
{
    int l=0,r=0,x,y;
    que[0]=beg;
    while(l<=r)
    {
        x=que[l++];
        if(x==n-1) return true;
        for(int y:g[x])
        {
            if((s>>y)&1) continue;
            s|=1LL<<y;que[++r]=y;
        }
    }
    return false;
}
int calc(int x,ll s1,ll s2)
{
    // if(!bfs(x,s1)) return inf;
    s2|=adj[n-1];
    int tot=0;
    for(int i=0;i<n;++i)
        if((s2>>i)&1) tot+=a[i];
    return tot;
}
void dfs(int x,ll s1,ll s2)
{
    if(cnt>=10000000) return;
    ++cnt;
    if(x==n-1)
    {
        // printf("%d %d ?\n",x,calc(x,s1,s2));
        ans=min(ans,calc(x,s1,s2));
        return;
    }
    ll h=s1*100+x;
    if(se.count(h)) return;
    se.insert(h);
    // printf("%d %d %d !!\n",x,calc(x,s1,s2),ans);
    if(calc(x,s1,s2)>=ans) return;
    
    for(int y:g[x])
    {
        if((s1>>y)&1) continue;
        dfs(y,s1|(1LL<<y),s2|adj[y]);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i) 
    {
        scanf("%d",&a[i]);
        adj[i]=1LL<<i;
    }
    int x,y;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        --x;--y;
        g[x].push_back(y);g[y].push_back(x);
        adj[x]|=1LL<<y;adj[y]|=1LL<<x;
    }
    for(int i=0;i<n;++i) 
        shuffle(g[i].begin(),g[i].end(),default_random_engine(0));
    ans=inf;
    dfs(0,1,adj[0]);
    printf("%d\n",ans);
    return 0;
}