首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >3315 时空跳跃者的魔法

3315 时空跳跃者的魔法

作者头像
attack
发布2018-04-12 16:43:58
6740
发布2018-04-12 16:43:58
举报

3315 时空跳跃者的魔法

时间限制: 1 s

空间限制: 32000 KB

题目等级 : 白银 Silver

题目描述 Description

背景:suntian正准备将飞翔带回圣殿,不料一声巨响,suntian的三维时空被飞翔炸开,飞翔再次出现在suntian面前,两人同时出手……随着两人昏天暗地的打斗,时空开始扭曲并产生波动,影响了suntian施咒,然而就是这一下,飞翔抓住了时机,释放巨大的能量将suntian送入了一个扭曲的四维时空……

描述:为了快一点追到飞翔,suntian希望在最短的时间内逃出这个四维时空。

他马上集中精力,在0.0000000000000001ms之内找到了这个时空的奇点。令他吃惊的是,这个空间竟然有n个奇点!这让suntian摸不着头脑。但作为圣殿战士,suntian也不是吃素的,他在冥思苦想之后得出了一个结论:只有在某个奇点处用咒术将其他n-1个奇点拉到这个奇点,才能将奇点打开。但是,将奇点拉拽到另一个奇点耗费的能量不同。能量W为:trunc(sqrt((x1-x2)^2+(y1-y2)^2+(z1-z2)^2))+abs(t1-t2) Tas。奇点拉在一起将被合并,suntian可以先把某些奇点合并再拉到他所处的奇点。为了抓捕到飞翔,suntian想用最少的能量来打开奇点,但是suntian能量已经所剩不多了。那么,suntian能否逃脱呢?

输入描述 Input Description

第一行,为n(0<n<=10^3,n∈N)。

第2至n+1行,为每行的坐标x,y,z,t(0<x,y,z,t<=10^4,x,y,z,t∈N)。 第n+2行,为suntian剩余能量L(0<L<maxlongint,L∈N)。

输出描述 Output Description

共一行。

 如果所用最少能量tot>L,那么输出“Death”;

 否则,输出tot。(tot<maxlongint)

样例输入 Sample Input

5

1 1 1 1

1 1 1 2

2 2 2 2

3 3 3 3

3 3 3 4

5Tas

样例输出 Sample Output

5Tas

数据范围及提示 Data Size & Hint

数据提示上面有。

分类标签 Tags 点此展开

注意最后字符串的转换

我利用了atof函数

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 const int MAXN=1000001;
 8 const int maxn=0x7fffffff;
 9 int x[MAXN];
10 int y[MAXN];
11 int z[MAXN];
12 int tas[MAXN];
13 struct node
14 {
15     int u;
16     int v;
17     double w;
18     int next;
19 }edge[MAXN];
20 int num=1;
21 int head[MAXN];
22 int f[MAXN];
23 int comp(const node & a, const node & b)
24 {
25     if(a.w<b.w)
26     return 1;
27     return 0;
28 }
29 int find(int x)
30 {
31     if(f[x]!=x)
32     f[x]=find(f[x]);
33     return f[x];
34 }
35 void unionn(int x,int y)
36 {
37     int fx=find(x);
38     int fy=find(y);
39     f[fx]=fy;
40 }
41 int main()
42 {
43     int n;
44     scanf("%d",&n);
45     for(int i=1;i<=n;i++)
46     {
47         scanf("%d%d%d%d",&x[i],&y[i],&z[i],&tas[i]);
48         f[i]=i;        
49     }
50     for(int i=1;i<=n;i++)
51     {
52         for(int j=1;j<=n;j++)
53         {
54             edge[num].u=i;
55             edge[num].v=j;
56             edge[num].w=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]))+abs(tas[i]-tas[j]);
57             edge[num].next=head[i];
58             head[i]=num++;
59         }
60     }
61     sort(edge+1,edge+num,comp);
62     int k=0;
63     double tot=0;
64     for(int i=1;i<=num;i++)
65     {
66         if(find(edge[i].u)!=find(edge[i].v))
67         {
68             unionn(edge[i].u,edge[i].v);
69             tot=tot+edge[i].w;
70             tot=floor(tot);
71             k++;
72         }
73         if(k==n-1)break;
74     }
75     char sr[101];
76     scanf("%s",sr);
77     double p=atof(sr);
78     if(tot>p)
79     {
80         printf("Death");
81     }
82     else
83     {
84         printf("%.0lfTas",tot);
85     }
86     return 0;
87 }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-04-17 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 3315 时空跳跃者的魔法
    • 分类标签 Tags 点此展开
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档