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;
}