P3489 [POI2009]WIE-Hexer 题解

#include<iostream>
#include<cstring>
#include<queue>
#define N 210
#define M 3010
using namespace std;
int dis[N][(1<<13)+10],ab[N];
int n,m,p,k,u1,v1,w1,s1,t1,n1;
struct EDEG{
    int v,w,gs,nxt;
}e[M*2];
int head[N],cnt;
void add(int u,int v,int w,int gs)
{
    e[++cnt].nxt=head[u];head[u]=cnt;
    e[cnt].v=v;e[cnt].w=w;e[cnt].gs=gs;
}
struct node{
    int val,status,dis;
    bool operator < (const node &t)const{
        return t.dis<dis;
    }
};
priority_queue <node> q;
void dij(int s)
{
    dis[1][0]=0;
    q.push({1,0,0});
    while(!q.empty())
    {
        node tt=q.top();q.pop();
        int u=tt.val,d=tt.status;
        dis[u][d|ab[u]]=dis[u][d];d|=ab[u];
        for(int i=head[u];i!=-1;i=e[i].nxt)
            if((e[i].gs&d)==e[i].gs)
                if(dis[e[i].v][d]>dis[u][d]+e[i].w)
                {
                    dis[e[i].v][d]=dis[u][d]+e[i].w;
                    q.push({e[i].v,d,dis[e[i].v][d]});
                }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>p>>k;
    for(int i=1;i<=k;i++)
    {
        cin>>u1>>s1;
        for(int j=1;j<=s1;j++)
        {
            cin>>v1;
            ab[u1]|=(1<<(v1-1));
        }
    }
    memset(head,-1,sizeof(head));
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=m;i++)
    {
        w1=0;
        cin>>u1>>v1>>t1>>s1;
        for(int j=1;j<=s1;j++)
            cin>>n1,w1|=(1<<(n1-1));
        add(u1,v1,t1,w1);
        add(v1,u1,t1,w1);
    }
    dij(1);
    int minn=1000000000;
    for(int i=0;i<=(1<<13);i++)
        minn=min(minn,dis[n][i]);
    if(minn!=1000000000)
        cout<<minn<<'\n';
    else    cout<<-1<<'\n';
    return 0;
}