题目名称	606. 燃烧
输入输出	`firez.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	cqw 于2011-11-07加入
开放分组	全部用户
提交状态
分类标签
	分享题解

通过：14，提交：29，通过率：48.28%
echo	100	0.005 s	0.81 MiB	Pascal
stone	100	0.007 s	0.51 MiB	C++
horizon<<	100	0.008 s	0.67 MiB	C++
Moonlight ヾ	100	0.009 s	0.67 MiB	C++
coastline>>	100	0.009 s	0.67 MiB	C++
_stranger	100	0.009 s	0.69 MiB	C++
啊吧啦吧啦吧	100	0.010 s	0.51 MiB	C++
Sunshine ヾ	100	0.011 s	8.29 MiB	Pascal
Des.	100	0.013 s	1.47 MiB	Pascal
阿狸	100	0.024 s	0.51 MiB	C++

本题关联比赛
20111107

关于燃烧的近10条评论(全部评论)
reamb 2011-11-07 19:25 1楼

606. 燃烧

★★ 输入文件：firez.in 输出文件：firez.out 简单对比
时间限制：1 s 内存限制：128 MiB

【问题描述】

Tom 是调皮的孩子，特别喜欢玩火，现在他手上有若干根长度分别为 1 和 sqrt(2) 的木棍，还有一张不能燃烧的平板，他把平板划分成长度为 1 的单元格，并标上座标。然后按以下规则把平板上的木棍组成一个连通图：木棍的两端必须放在单元格的顶点上。即长度为 1 的木棍放在单元格的某一边上，长度为 sqrt(2) 的木棍放在单元格的对角线上。

Tom 的点火规则是，只能从木棍的两端点火，而不能从木棍的中间点火。如图，不能在 A 点点火，但在 C 点或 B 点点火都是允许的。点火后，火会沿着木棍向前燃烧（每根都有自己的燃烧速度），并能点燃与它相接的其它木棍。

任务：写一程序计算从哪里开始点火，使得燃烧的总时间最短，输出最短时间。

Input Data

输入文件第一行为一个正整数 N ，表示组成图形的木棍数目，后面共有 N 行，每行 5 个数： X1 Y1 X2 Y2 T , 其中（ X1 , Y1 ）和（ X2 , Y2 ）分别表示木棍两端的坐标， T 表示木棍燃烧时间，是指从木棍的某一端点火燃烧到别一端，燃完所需的时间。

Output Data

输出文件是一个保留 4 位小数的实数，表示所有木棍完全燃烧的最少时间。

约束 1 ≤n≤40

保证图形是连通的，所有的木棍长度都是 1 或 sqrt(2)，没有任何两根木棍重合 .

-200≤ X1, Y1, X2, Y2 ≤200; 0≤ T ≤ 10^7 .

如果你的输出结果与标准答案相差小于 0.001 ，则认为你的结果正确。

样例 1

firez.in

firez.out

解释

0 0 1 1 1

1.0000

从任一端点火都行，燃烧时间都是 1

样例 2

firez.in

firez.out

解释

0 0 0 1 1

1 0 0 1 10

0 0 1 0 1

0 0 1 1 1

2 2 1 1 1

3.2500

在 (0,0) 位置点火

木棍 1, 3 和 4 将被点燃，燃烧 0.5 分钟后，木棍 2 将被从中间点燃向两端燃烧，再过 0.5 分钟，木棍 1, 3, 4 将被完全燃烧，木棍 5 将被点燃并在 1 分钟后燃烧完 ( 比木棍 2 早燃完 ) 。

木棍 2 从中间向两端燃烧 0.5 分钟以后，变成两小段，每段的燃烧时间是 4.5 分钟。但因为此时两小段木棍的另一端也同时被点燃，燃烧速度变成原来的两倍，还需 2.25 分钟的燃烧时间，所以总时间： 1 + 2 . 25 = 3 . 25

样例 3

firez.in

firez.out

解释

1 1 1 2 10

1 2 2 2 10

1 1 2 2 50

35.0000

在 (1,2) 位置点火，木棍 (1 1, 1 2) 和 (1 2, 2 2) 将燃烧 10 分钟。 . 最后一根木棍在 10 分钟后从两端被点燃，燃烧时间为 25 分钟。