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 long long LL;
const int maxn=50;
struct State{
    LL S;
    int cur,val;
    State (LL _S=0,int _cur=0,int _val=0):S(_S),cur(_cur),val(_val){}
    bool operator < (const State &rh)const{
        return val>rh.val;
    }
};
map<LL,int>Dist[maxn]; // Dist[cur][state]
int n,m;
int V[maxn];
LL G[maxn];
vector<int>E[maxn];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>V[i];
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        G[u]|=1LL<<v;E[u].push_back(v);
        G[v]|=1LL<<u;E[v].push_back(u);
    }
    int Init=0;
    for(int i=1;i<=n;i++)
    {
        G[i]|=1LL<<i;
        if(G[1]&(1LL<<i))Init+=V[i];
    }
    priority_queue<State>Q;
    Q.push(State(G[1],1,Init));
    Dist[1][G[1]]=Init;
    while(!Q.empty())
    {
        State now=Q.top();Q.pop();
        int u=now.cur;
        if(u==n)
        {
            cout<<now.val<<endl;
            break;
        }
        for(int i=0;i<(int)E[u].size();i++)
        {
            int v=E[u][i];
            LL newS=now.S|G[v];
            int newVal=0;
            for(int j=1;j<=n;j++)
                if(newS & (1LL<<j))
                    newVal+=V[j];
            if(Dist[v].find(newS)==Dist[v].end() || Dist[v][newS]>newVal)
            {
                Dist[v][newS]=newVal;
                Q.push(State(newS,v,newVal));
            }
        }
    }
    return 0;
}