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:
//??¶??´???3s   ?????´???256MB
//?¢????:???????????????,????±????1??°n?????°????????????,???????????????????????\????????????
//????????\??????????????????????°?
//??????:dp
//??¶???:???????????????i 
//??¶???:dp[i]??¨???1~n?????????????§£
//??????:dp[i]=value(allson)
//??¨??¬?§???¶,?????????????????????????????\????????????????????????,??±?????????????????°
//???????°?,?????\?????\?????¨????????¶????????¶?????????
//??\????????????????????????i??????????§£,???????????????????????\?????? 
#include<cstdio> 
#include<algorithm>
#include<vector>
#include<map>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
vector<int>G[45];
map<ll,bool>visit;
int dp[45],a[45];
int n,m;
void add(ll & x,int w){
	x|=(1LL<<w);
}
int update(ll x){
	int sum=0;
	for(int i=1;i<=n;i++)
		if(x&(1LL<<i))sum+=a[i];
	return sum;
}
void dfs(int u,ll now){	
	visit[now]=true;//????????¶????????°???,??????????¬??????? 
//	cout<<now<<endl;
	int lena=G[u].size();
	for(int i=0;i<lena;i++){
		ll tmp=now;
		int v=G[u][i];
		int lenb=G[v].size();
		for(int j=0;j<lenb;j++){
			int w=G[v][j];
			add(tmp,w);
		}
		add(tmp,v);
		int tot=update(tmp);
		if(tot<=dp[v]){
			dp[v]=tot;
			if(visit[tmp])continue;
			dfs(v,tmp);
		}
	}
}
int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int j=1;j<=m;j++){
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	memset(dp,127,sizeof(dp));
	G[0].push_back(1);
	dfs(0,0);
	printf("%d\n",dp[n]);
	return 0;
}