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>
#define ll long long
#define P pair < int , ll >
#define PP pair < int , P >
#define st first
#define nd second
//This code is written by Itst
using namespace std;

inline int read(){
	int a = 0;
	char c = getchar();
	bool f = 0;
	while(!isdigit(c) && c != EOF){
		if(c == '-')
			f = 1;
		c = getchar();
	}
	if(c == EOF)
		exit(0);
	while(isdigit(c)){
		a = (a << 3) + (a << 1) + (c ^ '0');
		c = getchar();
	}
	return f ? -a : a;
}

map < P , int > dp;
int N , M , ans , head[45] , val[45] , cntEd;
struct Edge{
	int end , upEd;
}Ed[2010];
ll fj[45];

inline void addEd(int a , int b){
	Ed[++cntEd].end = b;
	Ed[cntEd].upEd = head[a];
	head[a] = cntEd;
	fj[a] |= 1ll << b;
}

void Dijk(){
    priority_queue < PP > q;
	int all = 0;
	for(int i = 0 ; i < N ; ++i)
		if(fj[0] & (1 << i))
			all += val[i];
	dp.clear();
	dp[P(0 , fj[0])] = all;
	q.push(PP(-all , P(0 , fj[0])));
	while(!q.empty()){
		PP t = q.top();
		q.pop();
		if(-t.st > dp[t.nd])
			continue;
		int x = t.nd.st , cost = dp[t.nd];
		ll y = t.nd.nd;
		if(x == N - 1){
			ans = cost;
			return;
		}
		for(int i = head[x] ; i ; i = Ed[i].upEd){
			ll k = y | fj[Ed[i].end];
			int c = 0;
			for(int j = 0 ; j < N ; ++j)
				if(k & (1ll << j))
					c += val[j];
			if(!dp.count(P(Ed[i].end , k)) || dp[P(Ed[i].end , k)] > c){
				dp[P(Ed[i].end , k)] = c;
				q.push(PP(-c , P(Ed[i].end , k)));
			}
		}
	}
}

int main(){
	while(1){
		N = read();
		M = read();
		ans = 1e9;
		for(int i = 0 ; i < N ; ++i)
			val[i] = read();
		cntEd = 0;
		memset(head , 0 , sizeof(head));
		for(int i = 0 ; i < N ; ++i)
			fj[i] = 1ll << i;
		for(int i = 1 ; i <= M ; ++i){
			int a = read() - 1 , b = read() - 1;
			addEd(a , b);
			addEd(b , a);
		}
		Dijk();
		printf("%d\n" , ans);
	}
	return 0;
}