时间限制: 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
数据提示上面有。
注意最后字符串的转换
我利用了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 }