Description：

有 $n$ 个村庄 $m$ 条双向道路 $p$ 种怪物 $k$ 个铁匠，每个铁匠会居住在一个村庄里，你到了那个村庄后可以让他给你打造剑，每个铁匠打造的剑都可以对付一些特定种类的怪物，每条道路上都可能出现一些特定种类的怪物，每条道路都有一个通过所需要的时间，现在要从 $1$ 走到 $n$ ，初始的时候你没有剑，要求在经过一条道路的时候，对于任意一种可能出现在这条道路上的的怪物，你都有已经有至少一把剑可以对付他，求从 $1$ 走到 $n$ 的最短时间。

$1\leqslant k\leqslant n \leqslant 200,1\leqslant m\leqslant 3000,1\le p \le 13$

Solution：

观察到 $p$ 非常小，可以建一个 $2^p$ 层的图，每一层代表有这些剑的情况，那么这一层有某条边当且仅当这一层的剑可以杀掉这条边的怪物，那么铁匠就对应了在层之间转移，然后跑最短路就好。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m,a,b;

struct edge

{

	int to,nxt,v;

}e[(1 << 14) * 210 + (1 << 14) * 3010 * 2];

int edgenum = 0;

int lin[(1 << 14) * 210] = {0};

void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int d[(1 << 14) * 210];

bool inq[(1 << 14) * 210];

int main()

{

	scanf("%d%d%d%d",&n,&m,&a,&b);

	int tot = (1 << a) - 1;

	int x,y,w,p,z;

	for(int i = 1;i <= b;++i)

	{

		scanf("%d%d",&p,&w);

		int tmp = 0;

		for(int k = 1;k <= w;++k)

		{

			scanf("%d",&x);

			tmp |= (1 << (x - 1));

		}

		for(int k = 0;k <= tot;++k)

		{

			add(k * n + p,(k | tmp) * n + p,0);

		}

	}

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d%d",&x,&y,&p,&w);

		int tmp = 0;

		for(int k = 1;k <= w;++k)

		{

			scanf("%d",&z);

			tmp |= (1 << (z - 1));

		}

		for(int k = 0;k <= tot;++k)

		{

			if((k & tmp) == tmp)

			{

				add(k * n + x,k * n + y,p);

				add(k * n + y,k * n + x,p);

			}

		}

	}

	queue<int> q;q.push(1);

	memset(d,0x3f,sizeof(d));

	memset(inq,false,sizeof(inq));

	d[1] = 0;inq[1] = true;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		inq[k] = false;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].v)

			{

				d[e[i].to] = d[k] + e[i].v;

				if(!inq[e[i].to])

				{

					q.push(e[i].to);

					inq[e[i].to] = true;

				}

			}

		}

	}

	int ans = 0x3f3f3f3f;

	for(int k = 0;k <= tot;++k)

	{

		ans = min(ans,d[k * n + n]);

	}

	if(ans != 0x3f3f3f3f)cout << ans << endl;

	else puts("-1");

	return 0;

}