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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 45
#define BASE 2

int V,E;
int start,goal;
int ans;
vector<int> G[NUM];
bool used[NUM];
int counted[NUM]; //★★何番目のノードを探索する際に、コスト計上したか★★
int table[NUM];

void recursive(int node_id,int num_passed,int sum_cost){ //num_passed:0オリジンで、今回が何番目のノードか

	if(sum_cost >= ans)return;

	if(node_id == goal){

		ans = min(ans,sum_cost);
		return;
	}

	vector<int> WORK;
	int tmp_cost,next_node;
	for(int i = 0; i < G[node_id].size(); i++){ //次のノードのループ

		tmp_cost = sum_cost;
		next_node = G[node_id][i];
		if(used[next_node] == true || num_passed-counted[next_node] >= BASE)continue;
		used[next_node] = true;
		WORK.clear();

		//次に訪問するノードの隣接ノードのコストを計上する
		for(int k = 0; k < G[next_node].size(); k++){
			if(counted[G[next_node][k]] >= 0)continue;
			counted[G[next_node][k]] = num_passed;
			WORK.push_back(G[next_node][k]);
			tmp_cost += table[G[next_node][k]];
		}
		recursive(next_node,num_passed+1,tmp_cost);

		used[next_node] = false;
		for(int k = 0; k < WORK.size(); k++){
			counted[WORK[k]] = -1;
		}
	}
}


int main(){

	scanf("%d %d",&V,&E);

	start = 0;
	goal = V-1;

	for(int i = 0; i < V; i++){
		scanf("%d",&table[i]);
	}

	int from,to;

	for(int loop = 0; loop < E; loop++){

		scanf("%d %d",&from,&to);
		from--;
		to--;

		G[from].push_back(to);
		G[to].push_back(from);
	}

	ans = BIG_NUM;

	for(int i = 0; i < V; i++){
		used[i] = false;
		counted[i] = -1;
	}

	used[start] = true;
	counted[start] = 0;
	int first_cost = table[start];

	//スタートの隣接辺のコストを計上する(★固定★)
	for(int i = 0; i < G[start].size(); i++){
		counted[G[start][i]] = 0;
		first_cost += table[G[start][i]];
	}

	vector<int> WORK;
	int tmp_cost,next_node;
	for(int i = 0; i < G[start].size(); i++){ //次のノードのループ

		tmp_cost = first_cost;
		next_node = G[start][i];
		used[next_node] = true;
		WORK.clear();

		//次に訪問するノードの隣接ノードのコストを計上する
		for(int k = 0; k < G[next_node].size(); k++){
			if(counted[G[next_node][k]] >= 0)continue;
			counted[G[next_node][k]] = 1;
			WORK.push_back(G[next_node][k]);
			tmp_cost += table[G[next_node][k]];
		}
		recursive(next_node,2,tmp_cost);

		used[next_node] = false;
		for(int k = 0; k < WORK.size(); k++){
			counted[WORK[k]] = -1;
		}
	}

	printf("%d\n",ans);

	return 0;
}