题目描述
贝西喜欢去洞穴探险。这次她去的地方由 N 个洞穴组成，编号分别是 1 到 N，1 号洞穴是出发
的起点。
洞穴之间由 M 条隧道相连，双向通行，第 i 条隧道连接 A i 和 B i 。每条隧道有个尺寸，第 i 条
隧道的尺寸为 W i ，如果贝西的身材超过了隧道的尺寸，就钻不过去了。贝西的身材可用一个数字来
描述，一开始是 0。
前期准备时，贝西已在 K 个里洞穴存放了食物，她当然不会放过它们。当她吃掉一份食物后，
身材就会增加 1。在探险的过程中，她想吃掉尽量多的食物，但要保证最后能返回起点。请帮她计划
一下，什么样的路线才能吃到最多的食物？
注意，探险的路线可以重复，所以路过有食物时，可以留到下次路过的时候再吃。
输入
• 第一行：三个整数 N，M 和 K，1 ≤ N ≤ 100,1 ≤ M ≤ 1000,1 ≤ K ≤ 14
• 第二行到第 K+1 行：第 i+1 行有一个整数 C i ，表示在第 C i 号洞穴里有一份食物，1 ≤ C i ≤ N
• 第 K +2 行到第 K +M +1 行：第 i+K +1 行有三个整数 A i ，B i 和 W i ，1 ≤ A i ,B i ≤ N,1 ≤
W i ≤ 100
输出
• 单个整数：表示贝西最多能吃几份食物
样例输入
6 7 5 1 2 3 4 5 1 2 3 3 6 2 6 2 10 2 4 1 5 1 1 4 5 1 1 6 1
样例输出
4
提示
先吃 5 号洞里的，再吃 3，2，最后走回 1，
吃掉 1 里的最后一份食物
题解：
K<=14 很明显可以状压 ,然后发现想不出什么方程式，于是就上状压搜索，分析复杂度(1<<K)*N = 10^6 随便水过.
于是上记忆搜乱搞 F[i][j] 到i这个点状态为j 是否走过
注意：如果有食物在1号点,注意特判
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=,M=,Z=;
int gi(){
int str=;char ch=getchar();
while(ch>'' || ch<'')ch=getchar();
while(ch>='' && ch<='')str=str*+ch-,ch=getchar();
return str;
}
int n,m,k,w[N],head[N],num=,id[N];
struct Lin{
int next,to,dis;
}a[M<<];
void init(int x,int y,int z){
a[++num].next=head[x];
a[num].to=y;
a[num].dis=z;
head[x]=num;
}
bool mark[N][<<Z];int ans=;
void dfs(int x,int p,int tot)
{
if(mark[x][p])return ;
mark[x][p]=true;
if(x== && tot>=ans)
{
if(w[] && !(p&(<<(id[]-))))ans=tot+;
else ans=tot;
}
int u;
for(int i=head[x];i;i=a[i].next)
{
u=a[i].to;
if(tot>a[i].dis)continue;
dfs(u,p,tot);
if(p&(<<(id[x]-)))continue;
if(w[x] && tot<a[i].dis)dfs(u,p|(<<(id[x]-)),tot+);
}
}
int main()
{
int x,y,z;
n=gi();m=gi();k=gi();
for(int i=;i<=k;i++)x=gi(),w[x]=,id[x]=i;
for(int i=;i<=m;i++)
{
x=gi();y=gi();z=gi();
init(x,y,z);init(y,x,z);
}
dfs(,,);
printf("%d",ans);
return ;
}