Algorithm 版 (精华区)

发信人: Lerry (life is waiting...), 信区: Algorithm
标  题: 1298P-DominoEffect-ZJU
发信站: 哈工大紫丁香 (2002年10月11日11:25:39 星期五), 站内信件

Domino Effect
----------------------------------------------------------------------------
----
Time limit: 30 Seconds   Memory limit: 32768K
Total Submit: 37   Accepted Submit: 16
----------------------------------------------------------------------------
----
Did you know that you can use domino bones for other things besides playing 
Dominoes? Take a number of dominoes and build a row by standing them on end 
with only a small distance in between. If you do it right, you can tip the f
irst domino and cause all others to fall down in succession (this is where t
he phrase ``domino effect'' comes from).
While this is somewhat pointless with only a few dominoes, some people went 
to the opposite extreme in the early Eighties. Using millions of dominoes of
 different colors and materials to fill whole halls with elaborate patterns 
of falling dominoes, they created (short-lived) pieces of art. In these cons
tructions, usually not only one but several rows of dominoes were falling at
 the same time. As you can imagine, timing is an essential factor here.
It is now your task to write a program that, given such a system of rows for
med by dominoes, computes when and where the last domino falls. The system c
onsists of several ``key dominoes'' connected by rows of simple dominoes. Wh
en a key domino falls, all rows connected to the domino will also start fall
ing (except for the ones that have already fallen). When the falling rows re
ach other key dominoes that have not fallen yet, these other key dominoes wi
ll fall as well and set off the rows connected to them. Domino rows may star
t collapsing at either end. It is even possible that a row is collapsing on 
both ends, in which case the last domino falling in that row is somewhere be
tween its key dominoes. You can assume that rows fall at a uniform rate.
Input
The input contains descriptions of several domino systems. The first line of
 each description contains two integers: the number n of key dominoes (1 <= 
n < 500) and the number m of rows between them. The key dominoes are numbere
d from 1 to n. There is at most one row between any pair of key dominoes and
 the domino graph is connected, i.e. there is at least one way to get from a
 domino to any other domino by following a series of domino rows.
The following m lines each contain three integers a, b, and l, stating that 
there is a row between key dominoes a and b that takes l seconds to fall dow
n from end to end.
Each system is started by tipping over key domino number 1.
The input ends with an empty system (with n = m = 0), which should not be pr
ocessed.
Output
For each case output a line stating the number of the case (`System #1', `Sy
stem #2', etc.). Then output a line containing the time when the last domino
 falls, exact to one digit to the right of the decimal point, and the locati
on of the last domino falling, which is either at a key domino or between tw
o key dominoes. Adhere to the format shown in the output sample. If you find
 several solutions, output only one of them. Output a blank line after each 
system.
Sample Input
2 1
1 2 27
3 3
1 2 5
1 3 5
2 3 5
0 0
Sample Output
System #1
The last domino falls after 27.0 seconds, at key domino 2.
System #2
The last domino falls after 7.5 seconds, between key dominoes 2 and 3.

--
刚刚公布的消息：从明天凌晨0时起，中国移动的手机

开始实行单项收费，联通也将在近期内跟进。

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.249.235]