P3489 [POI2009]WIE-Hexer

大陆上有n个村庄，m条双向道路，p种怪物，k个铁匠，每个铁匠会居住在一个村庄里，你到了那个村庄后可以让他给你打造剑，每个铁匠打造的剑都可以对付一些特定种类的怪物，每条道路上都可能出现一些特定种类的怪物，每条道路都有一个通过所需要的时间，现在要从1走到n，初始的时候你没有剑，要求在经过一条道路的时候，对于任意一种可能出现在这条道路上的的怪物，你都有已经有至少一把剑可以对付他，求从1走到n的最短时间（打造剑不需要时间）

最短路上状压DP。

可以把当前对于可不可以消灭每种怪物压成一个状态，跟随最短路转移即可。

code：

#include 
    
     #include 
     
      #include 
      
       #define int long longusing namespace std;const int wx=20017;inline int read(){    int sum=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}    while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}    return sum*f;}int head[wx],dis[217][wx],vis[217][wx];int flag[wx];int num,n,m,p,WX,ans=0x3f3f3f3f,k;struct e{    int nxt,to,dis,flag;}edge[wx*2];void add(int from,int to,int dis,int flag){    edge[++num].nxt=head[from];    edge[num].to=to;    edge[num].dis=dis;    edge[num].flag=flag;    head[from]=num;}struct node{    int u,d,flag;    friend bool operator < (const node & a,const node & b){        return a.d>b.d;    }};priority_queue
       
         q;void Dij(){    for(int i=1;i<=n;i++)        for(int j=0;j
        
         dis[u][flaag]+edge[i].dis){                dis[v][flaag|flag[v]]=dis[u][flaag]+edge[i].dis;                q.push((node){v,dis[v][flaag|flag[v]],flaag|flag[v]});                if(v==n)ans=min(ans,dis[v][flaag|flag[v]]);            }        }    }    for(int i=0;i