大佬教程收集整理的这篇文章主要介绍了[bzoj5511]大中锋的游乐场,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
记可乐为1,汉堡为-1,即求过程中绝对值不超过k的最短路。
然后发现k的范围仅为10,也就是说过程中合法的值仅有21种,因此跑一遍dij或spfa(嘿嘿嘿)即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define pi pair<int,int> 4 #define mp make_pair 5 #define fi first 6 #define se second 7 #define N 10005 8 queue<pi >q; 9 struct ji{ 10 int nex,to,len; 11 }edge[N*20]; 12 int E,t,n,m,k,x,y,z,ans,d[n][41],vis[n][41],head[n],p[n]; 13 void add(int x,int y,int z){ 14 edge[E].nex=head[x]; 15 edge[E].to=y; 16 edge[E].len=z; 17 head[x]=E++; 18 } 19 int main(){ 20 scanf("%d",&t); 21 while (t--){ 22 scanf("%d%d%d",&n,&m,&k); 23 memset(d,0x3f,sizeof(d)); 24 memset(head,-1,sizeof(head)); 25 memset(vis,0,sizeof(vis)); 26 E=0; 27 for(int i=1;i<=n;i++){ 28 scanf("%d",&p[i]); 29 p[i]=p[i]*2-3; 30 } 31 for(int i=1;i<=m;i++){ 32 scanf("%d%d%d",&x,&y,&z); 33 add(x,z); 34 add(y,z); 35 } 36 scanf("%d%d",&y); 37 d[x][p[x]+20]=0; 38 vis[x][p[x]+20]=1; 39 q.push(mp(x,p[x]+20)); 40 while (!q.empty()){ 41 pi o=q.front(); 42 q.pop(); 43 vis[o.fi][o.se]=0; 44 for(int i=head[o.fi];i!=-1;i=edge[i].neX){ 45 x=edge[i].to; 46 if ((abs(o.se+p[x]-20)<=k)&&(d[o.fi][o.se]+edge[i].len<d[x][o.se+p[x]])){ 47 d[x][o.se+p[x]]=d[o.fi][o.se]+edge[i].len; 48 if (!vis[x][o.se+p[x]]){ 49 q.push(mp(x,o.se+p[x])); 50 vis[x][o.se+p[x]]=1; 51 } 52 } 53 } 54 } 55 ans=0x3f3f3f3f; 56 for(int i=20-k;i<=k+20;i++)ans=@H_147_61@min(ans,d[y][i]); 57 if (ans==0x3f3f3f3f)ans=-1; 58 printf("%d\n",ans); 59 } 60 }
以上是大佬教程为你收集整理的[bzoj5511]大中锋的游乐场全部内容,希望文章能够帮你解决[bzoj5511]大中锋的游乐场所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。