Luogu P3489 [POI2009]WIE-Hexer

题目链接：传送门

把剑压成一个状态就好了
最短路更新的时候看是不是符合条件
代码里还有点注释

/**
 * @Date:   2019-03-30T11:29:51+08:00
 * @Last modified time: 2019-03-30T11:29:53+08:00
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define A 1000010
#define B 2010

using namespace std;
typedef long long ll;
struct node {
    int next, to, w, sta;
}e[A];
int head[A], num;
void add(int fr, int to, int w, int sta) {
    e[++num].next = head[fr];
    e[num].to = to;
    e[num].w = w;
    e[num].sta = sta;
    head[fr] = num;
}
int n, m, p, k, w, q, sword[A], x, y, t, s, vis[210][20000], dis[210][20000], ans;
struct Node {
    int now, sta;
};
queue<Node> qq;
void spfa(int s) {
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    qq.push(Node{1, sword[1]});
    dis[s][sword[1]] = 0;
    while (!qq.empty()) {
        Node fr = qq.front(); qq.pop(); vis[fr.now][fr.sta] = 0;
        for (int i = head[fr.now]; i; i = e[i].next) {
            int ca = e[i].to; //and前面是必须要符合这条路的通过条件，后面是更新最短路，位运算看不懂可以自己手试几个
            if ((e[i].sta & fr.sta) == e[i].sta and dis[ca][sword[ca] | fr.sta] > dis[fr.now][fr.sta] + e[i].w) {
                dis[ca][sword[ca] | fr.sta] = dis[fr.now][fr.sta] + e[i].w;
                if (!vis[ca][sword[ca] | fr.sta]) {
                    vis[ca][sword[ca] | fr.sta] = 1;
                    qq.push(Node{ca, sword[ca] | fr.sta});
                }
            }
        }
    }
}

int main(int argc, char const *argv[]) {
	cin >> n >> m >> p >> k;
    for (int i = 1; i <= k; i++) {
        cin >> w >> q;
        while (q--) {
            cin >> x;
            sword[w] |= 1 << (x - 1);//存储当前状态
        }
    }
    while (m--) {
        cin >> x >> y >> t >> s; int sta = 0;
        while (s--) {
            cin >> q;
            sta |= 1 << (q - 1);
        }
        add(x, y, t, sta); add(y, x, t, sta);
    }
    spfa(1); ans = dis[n][0];
    for (int i = 1; i < 1 << p; i++) ans = min(ans, dis[n][i]);
    if (ans >= 0x3f3f3f3f) puts("-1");
    else cout << ans << endl;
    return 0;
}