P3489

将每一把剑状态压缩，跑最短路，怎么写都70pts，上次提问没人回复

#include <bits/stdc++.h>
using namespace std;
const int N = 210;
int n, m, p, k, sword[N], dist[N][10010];
bool vis[N][10010];
struct edge_node { int v, w, enemy; };
struct hero_node { int d, pos, sword; };
struct cmp {
	bool operator() (const hero_node& a, const hero_node& b) const {
		return a.d > b.d;
	}
};
vector<edge_node> e[N];
int ans = 0x3f3f3f3f;
#define mp(a, b, c) (hero_node){a, b, c}
void dijkstra() {
	memset(dist, 0x3f, sizeof dist);
	dist[1][sword[1]] = 0;
	priority_queue<hero_node, vector<hero_node>, cmp> Q;
	Q.push(mp(dist[1][sword[1]], 1, sword[1]));
	while(!Q.empty()) {
		int u = Q.top().pos, s = Q.top().sword; Q.pop();
		if(u == n) { ans = dist[u][s]; printf("%d\n", ans); return; }
		if(vis[u][s]) continue;
		vis[u][s] = true;
		for(unsigned i = 0; i < e[u].size(); i ++ ) {
			int v = e[u][i].v, w = e[u][i].w, en = e[u][i].enemy;
			int ns = s | sword[v];
			if((s | en) > s) continue;
			if(dist[v][ns] > dist[u][s] + w) {
				dist[v][ns] = dist[u][s] + w;
				Q.push(mp(dist[v][ns], v, ns));
			}
		}
	}
}
int main() {
	scanf("%d%d%d%d", &n, &m, &p, &k);
	for(int i = 1; i <= k; i ++ ) {
		int w, q; scanf("%d%d", &w, &q);
		for(int j = 1; j <= q; j ++ ) {
			int t; scanf("%d", &t);
			sword[w] |= 1 << (t - 1);
		}
	}
	for(int i = 1; i <= m; i ++ ) {
		int x, y, t, s, st = 0;
		scanf("%d%d%d%d", &x, &y, &t, &s);
		for(int j = 1; j <= s; j ++ ) {
			int tt; scanf("%d", &tt);
			st |= 1 << (tt - 1);
		}
		e[x].push_back((edge_node){y, t, st});
		e[y].push_back((edge_node){x, t, st});
	}
	dijkstra();
	for(int i = 0; i <= 10000; i ++ ) ans = min(ans, dist[n][i]);
	if(ans > 1e9) puts("-1");
//	else printf("%d\n", ans);
	return 0;
}