*原题链接*
最短路+状态压缩
不愧是POI的题，看题面知道要求加了一些限制的最短路，看数据范围很容易想到状态压缩。
求解最短路就用堆优化dijkstra好了。
至于状态压缩，我们对原数组再开一维，表示此时“剑的集合”，相应的
数组也要多开一维。由于此时的最短路有状态的限制，所以我们要用三元组来维护，如果不想写结构体也可以pair<pair<int,int>,int>。输入时存储边上的“怪物集合”，以及一个村庄的“铁匠集合”，在来到新村庄时或上铁匠集合，在最短路转移时判断能否走，这道题就做完了。
需要一些位运算技巧，详细见代码。
#include<bits/stdc++.h>
using namespace std;
#define PII pair<pair<int,int>,int>
const int N=210,M=(1<<14),INF=0x3f3f3f3f;int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();return x*f;
}int n,m,p,k,f[N][M],village[N],head[N],tot,vis[N][M];
struct node{int to,nxt,w,state;
}edge[N*N];
void add(int x,int y,int w,int s){edge[++tot].to=y;edge[tot].w=w;edge[tot].state=s;//怪物集合edge[tot].nxt=head[x];head[x]=tot;
}int dijkstra(int s){priority_queue<PII,vector<PII>,greater<PII> > q;q.push(make_pair(make_pair(0,s),0)),f[s][0]=0;while(!q.empty()){int t=q.top().first.second,s=q.top().second,cost=q.top().first.first;q.pop();if(t==n) return cost;if(vis[t][s]) continue;vis[t][s]=1,s|=village[t];//别忘了加上这个村庄对应的集合for(int i=head[t];i;i=edge[i].nxt){int y=edge[i].to;if((edge[i].state|s)!=s) continue;//当前state不是s的子集，无法通过这条路if(f[y][s|village[y]]>cost) f[y][s|village[y]]=cost+edge[i].w,q.push(make_pair(make_pair(f[y][s|village[y]],y),s));}}return -1;
}int main(){n=read(),m=read(),p=read(),k=read();for(int i=1;i<=k;i++){int x=read(),y=read();for(int j=1;j<=y;j++){int s=read();village[x]|=(1<<(s-1));}}for(int i=1;i<=m;i++){int x=read(),y=read(),w=read(),l=read(),state=0;for(int j=1;j<=l;j++){int s=read();state|=(1<<(s-1));}add(x,y,w,state),add(y,x,w,state);}memset(f,0x3f,sizeof(f));cout<<dijkstra(1)<<endl;return 0;
}