直接爆搜的复杂度是2^n，对于n<=40的数据过不了。
考虑优化一下。
发现如果走了一个点后，以后是不可能再经过与它相邻的点的，因为这样走显然不如直接走那个与它相邻的点。
这样每走一步就可以删掉d[x]个点，d[x]为x的度数。
这样做的复杂度O(n)=k*O(n-k)
在k=3的时候取到最大是，约等于3^13，可以通过。

#include<bits/stdc++.h>
#define N 110000
#define L 100000
#define eps 1e-7
#define inf 1e9+7
#define db double
#define ll long long
#define ldb long double
using namespace std;
inline int read()
{
    char ch=0;
    int x=0,flag=1;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*flag;
}
struct edge{int to,nxt;}e[N*2];
int num,head[N];
inline void add(int x,int y){e[++num]={y,head[x]};head[x]=num;}
int n,m,ans=inf,w[N],vis[N];
void dfs(int x,int s)
{
    if(++vis[x]==1)s+=w[x];
    for(int i=head[x];i!=-1;i=e[i].nxt){int to=e[i].to;if(++vis[to]==1)s+=w[to];}
    if(x==n)
    {
        ans=min(ans,s);
        vis[x]--;for(int i=head[x];i!=-1;i=e[i].nxt)vis[e[i].to]--;return;
        
    }
    for(int i=head[x];i!=-1;i=e[i].nxt){int to=e[i].to;if(vis[to]==1)dfs(to,s);}
    vis[x]--;for(int i=head[x];i!=-1;i=e[i].nxt)vis[e[i].to]--;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)w[i]=read();
    num=-1;memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        add(x,y);add(y,x);
    }
    dfs(1,0);printf("%d\n",ans);
    return 0;
}

优质内容筛选与推荐>>
1、DropDownList 无刷新三级分类
2、[导入]如何给表、列加注释？http://www.oradb.net
3、encodeURIComponent的用法
4、win10外接键盘失灵
5、if-else(python)的几种写法

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

阅读

已发送

发送中