正题

题目大意

有k中轻功，n个木桩，每种轻功可以消耗 $w_i\ s$ 飞过 $a_i$ 个木桩，有些木桩有不可以被某种轻功飞过的限制，然后切换一次轻功要 $W\ s$

解题思路

将图分成 $k$ 层，每层表示在不同的轻功状态，然后根据提议建图就好了。

code

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #define K 210#define N 510#define p(x,y) (x-1)*n+yusing namespace std;struct node{
   	int to,w,next;}a[N*K*K+N*K];vector
        
          no[N];queue
         
           q;int n,tot,W,ar[K],w[K],ls[N*K],f[N*K],k,x,y,Q;bool v[N*K];void addl(int x,int y,int w){ a[++tot].to=y;a[tot].w=w; a[tot].next=ls[x];ls[x]=tot;}void spfa()//SPFA{ memset(f,127/3,sizeof(f)); for(int i=1;i<=k;i++) q.push(p(i,1)),f[p(i,1)]=0,v[p(i,1)]=1; while(!q.empty()) { int x=q.front(); q.pop();v[x]=0; for(int i=ls[x];i;i=a[i].next) { int y=a[i].to; if(f[x]+a[i].w
          
           no[i][now]) now++; if(now
           
            <=j+ar[i]) continue; addl(p(i,j),p(i,j+ar[i]),w[i]); } } for(int ki=1;ki<=n;ki++) for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) if(i!=j) addl(p(i,ki),p(j,ki),W); spfa(); int ans=2147483647; for(int i=1;i<=k;i++) ans=min(ans,f[p(i,n)]); if(ans>2147483647/4) printf("-1"); else printf("%d",ans);}