[bzoj5511]大中锋的游乐场_C

概述记可乐为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

记可乐为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=min(ans,d[y][i]);57         if (ans==0x3f3f3f3f)ans=-1;58         printf("%d\n",ans);59     }60 }