加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

[bzoj5511]大中锋的游乐场

发布时间:2020-12-16 10:48:43 所属栏目:百科 来源:网络整理
导读:记可乐为 1 ,汉堡为 -1 ,即求过程中绝对值不超过 k 的最短路。 然后发现 k 的范围仅为 10 ,也就是说过程中合法的值仅有 21 种,因此跑一遍 dij 或 spfa (嘿嘿嘿)即可。 1 #includebits/stdc++.h 2 using namespace std; 3 #define pi pairint,int 4 #de

记可乐为1,汉堡为-1,即求过程中绝对值不超过k的最短路。

然后发现k的范围仅为10,也就是说过程中合法的值仅有21种,因此跑一遍dijspfa(嘿嘿嘿)即可。

 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("%dn",ans);
59     }
60 }
View Code

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读