首先 $p$ 很小，考虑状压。

跑 $\text{Dijskra}$，但是注意搜索时的每一个状态（也就是放在优先队列里的元素）要维护三个值：

• 目前所在的点。
• 到起点的距离。
• 当前剑的集合。

每一个点的每一条出边也要维护三个信息：

• 边的终点。
• 边的长度。
• 边上的妖怪的集合。

而且 $dis$ 数组也要开两维！

因为到达同一个点而获得不同种类的剑，所要走的距离显然是不同的。

枚举每一条出边，如果边上的妖怪集合是当前剑的集合的子集，就可以入队，并得到终点上的所有剑。

否则不能放行，因为你砍不死路上的所有妖怪。

另外注意，在起点时自动获得起点的剑，而不是轻装上阵。

时间复杂度为 $\mathcal{O}(2^p(n+m)\log n)$ 即 $\mathcal{O}(\texttt{能过})$。

还有由于是三元组，所以要写结构体，还要重载运算符。

顺便吐槽一下某些题解中的 pair<pair<int,int>,int>

见代码

#include <bits/stdc++.h>
using namespace std;
int n, m, p, k;
int x, y, z, c, t;
int arr[210];
int dis[210][8192];
struct node {
	int x;
	int d;
	int t;
};
bool operator < (node a, node b) {
	return a.d > b.d;
}
vector<node> G[210];
priority_queue<node> Q;
int main() {
	cin >> n >> m >> p >> k;
	while (k--) {
		cin >> x >> c;
		while (c--) {
			cin >> t;
			arr[x] |= (1<<(t-1));
		}
	}
	while (m--) {
		cin >> x >> y >> z >> c;
		k = 0;
		while (c--) {
			cin >> t;
			k |= (1<<(t-1));
		}
		G[x].push_back((node){y, z, k});
		G[y].push_back((node){x, z, k});
	}
	memset(dis, 0x3F, sizeof(dis));
	Q.push((node){1, 0, arr[1]});
	while (!Q.empty()) {
		node N = Q.top();
		Q.pop();
		int X = N.x;
		int D = N.d;
		int T = N.t;
		if (dis[X][T] <= D) continue;
		dis[X][T] = D;
		if (X == n) {
			cout << D << endl;
			return 0;
		}
		for (int i = 0; i < G[X].size(); i++) {
			if ((T | G[X][i].t) == T) Q.push((node){G[X][i].x, D + G[X][i].d, T | arr[G[X][i].x]});
		}
	}
	cout << -1 << endl;
	return 0;
}