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 <iostream>
#include <string.h>
#include <assert.h>
#include <vector>
#include <stdio.h>
#include <set>
using namespace std;

typedef long long LL;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef float fl;
typedef double ld;
typedef long double LD;
typedef pair<int,int> pii;
#define lld "%lld"
#define ui(n) ((unsigned int)(n))
#define LL(n) ((long long)(n))
#define ull(n) ((unsigned long long)(n))
#define fl(n) ((float)(n))
#define ld(n) ((double)(n))
#define LD(n) ((long double)(n))
#define char(n) ((char)(n))
#define Bool(n) ((bool)(n))
#define fixpoint(n) fixed<<setprecision(n)

const int INF=1061109567;
const LL LINF=4557430888798830399;
const ld eps=1e-15;
#define MOD (1000000007)
#define PI (3.1415926535897932384626433832795028841971)

#define MP make_pair
#define MT make_tuple
#define All(a) (a).begin(),(a).end()
#define pall(a) (a).rbegin(),(a).rend()
#define log2(x) log(x)/log(2)
#define Log(x,y) log(x)/log(y)
#define sz(a) ((int)(a).size())
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define rep1(i,n) for(int i=1;i<=((int)(n));i++)
#define repa(i,a,n) for(int i=((int)(a));i<((int)(n));i++)
#define repa1(i,a,n) for(int i=((int)(a));i<=((int)(n));i++)
#define repd(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define repd1(i,n) for(int i=((int)(n));i>=1;i--)
#define repda(i,n,a) for(int i=((int)(n));i>((int)(a));i--)
#define repda1(i,n,a) for(int i=((int)(n));i>=((int)(a));i--)
#define FOR(i,a,n,step) for(int i=((int)(a));i<((int)(n));i+=((int)(step)))
#define repv(itr,v) for(__typeof((v).begin()) itr=(v).begin();itr!=(v).end();itr++)
#define repV(i,v) for(auto i:v)
#define repE(i,v) for(auto &i:v)
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x) MS(x,0)
#define MINF(x) MS(x,63)
#define SF scanf
#define PF printf
/************************************************************Begin************************************************************/
const int maxn=45;

int n,m,c[maxn],dist[maxn];
vector<int> e[maxn];
set<LL> vis[maxn];

inline int calc(LL cho)
{
	int res=0;
	rep1(i,n) if(cho&(1LL<<i)) res+=c[i];
	return res;
}

inline void dfs(int x,LL cho)
{
	vis[x].insert(cho);

	rep(_i,e[x].size())
	{
		int i=e[x][_i];

		LL ccho=cho;

		rep(_j,e[i].size())
		{
			int j=e[i][_j];
			ccho|=(1LL<<j);
		}
		ccho|=(1LL<<i);

		int cres=calc(ccho);
		if(cres<=dist[i])
		{
			dist[i]=cres;
			if(vis[i].find(ccho)==vis[i].end()) dfs(i,ccho);
		}
	}
}

int main()
{
	SF("%d%d",&n,&m);
	rep1(i,n) SF("%d",&c[i]);
	rep(i,m)
	{
		int a,b;SF("%d%d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}

	MINF(dist);
	dist[0]=0;

	e[0].push_back(1);
	dfs(0,0);

	PF("%d\n",dist[n]);

	return 0;
}
/*************************************************************End**************************************************************/