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;

vector< vector<int> > G;
vector<int> C;

const ll inf = 1e18;

int N;
//ll ans[40][40];
ll ans = inf;
vector<bool> used1;
vector<int> used2;

ll dfs(int s, int t, int prev, ll cost) {
	if (cost >= ans) return ans;
	for (int i = 0; i < G[s].size(); ++i) {
		int v = G[s][i];
		if (v != prev && used1[v]) {
			return inf;
		}
	}
	if (used2[s]++ == 0) {
		cost += C[s];
	}
	for (int i = 0; i < G[s].size(); ++i) {
		int v = G[s][i];
		if (used2[v]++ == 0) {
			cost += C[v];
		}
	}
	if (cost >= ans) {
		--used2[s];
		for (int i = 0; i < G[s].size(); ++i) {
			--used2[G[s][i]];
		}
		return ans;
	}
	if (s == t) {
		--used2[s];
		for (int i = 0; i < G[s].size(); ++i) {
			--used2[G[s][i]];
		}
		return cost;
	}
	ll res = inf;
	for (int i = 0; i < G[s].size(); ++i) {
		int to = G[s][i];
		if (!used1[to]) {
			used1[to] = true;
			res = min(res, dfs(to, t, s, cost));
			used1[to] = false;
		}
	}
	--used2[s];
	for (int i = 0; i < G[s].size(); ++i) {
		--used2[G[s][i]];
	}
	if (s == 0 && t == N-1) ans = min(ans, res);
	if (s == 0) {
		assert(t == N-1);
		for (int i = 0; i < N; ++i) {
			assert(used2[i] == 0);
			assert(used1[i] == i==0);
		}
	}
	return res;
}

int main() {
	int M; cin >> N >> M;
	C.resize(N);
	G.resize(N);
	for (int i = 0; i < N; ++i) {
		cin >> C[i];
	}
	for (int i = 0; i < M; ++i) {
		int from, to; cin >> from >> to; --from, --to;
		G[from].push_back(to);
		G[to].push_back(from);
	}
//	fill(ans[0], ans[40], inf);
	used1 = vector<bool>(N, false); used1[0] = true;
	used2 = vector<int>(N, 0);
	cout << dfs(0, N-1, -1, 0) << endl;
}