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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int t,head[50],w[50];

struct edges{
	int to,next;
}e[(50*50)<<1];

void add(int x,int y){
	e[++t] = (edges){y,head[x]};
	head[x] = t;
}

int n,m,ans=1000000,now;
int vis[50],step;
void dfs(int x){
	step++;
	//cout<<x<<' '<<step<<endl;
	if(x==n){
		for(int p=head[x]; p; p=e[p].next) if(!vis[e[p].to])
			now+=w[e[p].to]; 
		ans=min(ans,now);
		for(int p=head[x]; p; p=e[p].next) if(!vis[e[p].to])
			now-=w[e[p].to];
		step--;
		//printf("vis[2]=%d\n",vis[2]);
		return;
	}
	for(int p=head[x]; p; p=e[p].next) if(!vis[e[p].to]){
		vis[e[p].to]=step;
		now+=w[e[p].to];
	}
	for(int p=head[x]; p; p=e[p].next) if(vis[e[p].to]==step){
		
		dfs(e[p].to);
		//printf("**step=%d  next(%d)=%d  vis[]=%d\n",step,x,e[e[p].next].to,vis[e[e[p].next].to]);
	}
	for(int p=head[x]; p; p=e[p].next) if(vis[e[p].to]==step){
		vis[e[p].to]=0;
		now-=w[e[p].to];
	}
	step--;
	//cout<<step<<endl;
}
int main(){
	int x,y;
	cin>>n>>m;
	for(int i=1;i<=n;++i)scanf("%d",&w[i]);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	now=w[1];
	vis[1]=1;
	dfs(1);
	cout<<ans<<endl;
	return 0;
}