wordpress全站腾讯云cdn,温州网页制作人才招聘,腾讯cdn WordPress,关于做外汇现货的网站正题 题目大意
有k中轻功#xff0c;n个木桩#xff0c;每种轻功可以消耗wisw_i\ swi s飞过aia_iai个木桩#xff0c;有些木桩有不可以被某种轻功飞过的限制#xff0c;然后切换一次轻功要WsW\ sW s 解题思路
将图分成kkk层#xff0c;每层表示在不同的轻功状态n个木桩每种轻功可以消耗wisw_i\ swi s飞过aia_iai个木桩有些木桩有不可以被某种轻功飞过的限制然后切换一次轻功要WsW\ sW s 解题思路
将图分成kkk层每层表示在不同的轻功状态然后根据提议建图就好了。 code
#includecstdio
#includevector
#includecstring
#includequeue
#includealgorithm
#define K 210
#define N 510
#define p(x,y) (x-1)*ny
using namespace std;
struct node{int to,w,next;
}a[N*K*KN*K];
vectorint no[N];
queueint 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].toy;a[tot].ww;a[tot].nextls[x];ls[x]tot;
}
void spfa()//SPFA
{memset(f,127/3,sizeof(f));for(int i1;ik;i)q.push(p(i,1)),f[p(i,1)]0,v[p(i,1)]1;while(!q.empty()){int xq.front();q.pop();v[x]0;for(int ils[x];i;ia[i].next){int ya[i].to;if(f[x]a[i].wf[y]){f[y]f[x]a[i].w;if(!v[y]){q.push(y);v[y]true;}}}}
}
int main()
{scanf(%d%d%d,n,k,W);n;for(int i1;ik;i)scanf(%d%d,ar[i],w[i]);scanf(%d,Q);for(int i1;iQ;i){scanf(%d%d,x,y);x;no[y].push_back(x);}for(int i1;ik;i){sort(no[i].begin(),no[i].end());int now0;for(int j1;jn-ar[i];j){while(nowno[i].size()jno[i][now]) now;if(nowno[i].size()no[i][now]jar[i]) continue;addl(p(i,j),p(i,jar[i]),w[i]);}}for(int ki1;kin;ki)for(int i1;ik;i)for(int j1;jk;j)if(i!j)addl(p(i,ki),p(j,ki),W);spfa();int ans2147483647;for(int i1;ik;i)ansmin(ans,f[p(i,n)]);if(ans2147483647/4) printf(-1);else printf(%d,ans);
}
