Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Escape of Life and Death
Description During his ambitious adventure in search of treasure, Yangyang discovered an ancient underground palace. After thoroughly exploring the palace, he found that it was constructed with elaborately decorated chambers connected by fortified corridors. Out of an explorer’s instinct, he sketched a complete map of the palace before entering the largest and most magnificent chamber, which lied in the heart of the palace. Standing at the center of the chamber, Yangyang looked around and was profoundly amazed by those vivid, huge statues of the gods. He recognized the tallest one, which depicted God Proxima holding his sacred cane. All of a sudden, a voice took Yangyang by surprise, “Leave now, you stupid human!” It was loud but sounded as if it came from the distance. A thought of danger immediately flashed through Yangyang’s mind: his intrusion into the palace had triggered a spell of destruction. Now an earthquake was emerging from right under the chamber and growing more and more violent. He must escape from underground for life as quickly as possible. Yangyang knew that seismic waves propagated isotropically at a constant speed. If they spread across any chamber, the chamber would collapse, trap anybody inside and become impassable. However, the corridors were adequately solid to stand any impact of earthquake. Driven by his fearless but obstinate character, Yangyang would only allow himself to run from one chamber to another one which was farther away from the epicenter except when he was going to run toward chamber Yangyang had measured the location of each chamber and estimated the time he needed to run through each corridor. How soon could he accomplish the escape of life and death? Input The input consists of a single test case. The first line of input contains three integers y) (−10_{i}^{9} ≤ x, _{i}y ≤ 10_{i}^{9}, ∀1 ≤ i ≤ n). The following m lines each contains three integers a, _{i}b, _{i}t (0 ≤ _{i}a, _{i}b ≤ _{i}n + 1, 1 ≤ t ≤ 1,000, ∀1 ≤ _{i}i ≤ m). The last line contains two pairs of integers (x_{0}, y_{0}), (x_{n+1}, y_{n+1}) (−10^{9} ≤ x_{0}, y_{0}, x_{n+1}, y_{n+1} ≤ 10^{9}).There were y). Corridor _{i}i (1 ≤ i ≤ m) connected chambers a and _{i}b, and Yangyang needed _{i}t units of time to run through it. Seismic waves propagated at constant speed _{i}v.Output If Yangyang could escape, output the minimum time he needed; otherwise, output “ Sample Input 1 2 1 3 4 0 1 5 1 2 5 0 0 6 8 Sample Output Impossible Hint As can be inferred from the sample test case, if seismic waves reached a chamber at the very moment Yangyang began to escape from it, he would still get trapped. Source POJ Founder Monthly Contest – 2008.03.16, Gao Yihan |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator