求完整代码。。。
Domino效应
(Domino Effect)
你知道用Domino骨牌除了玩Domino游戏外还能干其它事吗？把一些骨牌排成一列，相邻骨牌间相距很小的距离。如果你排的恰到好处，当你对倒第一块骨牌之后，后面的骨牌依次倒下（称为“Domino效应”）。
如果只有很少的骨牌，这就显得似乎没什么意义。一些人用数以万计的不同颜色不同材料的骨牌排满整个大厅，摆出各种图案，创造（虽然短命）艺术。在这些“建筑”中通常会有不止一排骨牌同时倒下。正如你所想象的那样，计时在这里是一个必不可少的因素。
现在轮到你工作了。你必须写一个程序，对于给定的一个骨牌系统，计算最后一块骨牌倒下的时间。系统中有一些“关节骨牌”，它们由另一些骨牌排连接。当一个关节骨牌倒下后，与它相连的骨牌排开始倒（除了那些已经倒的），“倒”将传到其它关节骨牌，并使它们倒。你可假定所有的骨牌倒下的时间相等。
输入格式
从文件domino.in输入。第一行为关节骨牌的个数n (1 £ n < 500)，和连接它们的骨牌排的个数m。关节骨牌的编号从1到n。下面有m行描述m个骨牌排。每行由三个整数a, b, l，其中a, b为该骨牌排连接的关节骨牌编号，l表示从a倒到b（或从b倒到a）需要l秒。每两个关节骨牌间至多有一个骨牌排。任两个关节骨牌之间至少有一条“路”（一序列相连的骨牌排）连接。
开始时，关节骨牌１将被推倒。
输出格式
输出到文件domino.out。按样例中的格式输出最后一块骨牌倒下的时刻和位置。
样例输入与输出
|
domino.in |
domino.out |
|
2 1 1 2 27 |
The last domino falls after 27.0 seconds, at key domino 2. |
|
3 3 1 2 5 1 3 5 2 3 5 |
The last domino falls after 7.5 seconds, between key dominoes 2 and 3. |
解答
这道题较简单，我们可以先构造图G=(V,E)，G的顶点就是所有的关节骨牌，如果两个关节骨牌之间有骨牌排连接，则相应点之间有无向边，从关节骨牌a倒到关节骨牌b的用时为无向边的权w(ab)。
最后一个倒下的骨牌可能为
(i) 某个关节骨牌k，其倒下的时间为顶点1到顶点k的最短路长；或者是
(ii) 某个骨牌排ab中的骨牌。假设关节骨牌a和关节骨牌b的倒下时间分别为d(a)和d(b)，d(a)和d(b)分别为顶点1到顶点a和顶点b的最短路长，则骨牌排ab中最后一块倒下的骨牌的倒下时间为max{d(a),d(b)}+[w(ab)+|d(a)-d(b)|]/2
假设我们已经求出了顶点1到所有顶点的最短路长d(1),d(2),…,d(n)，记L(a,b)=max{d(a),d(b)}+[w(ab)+|d(a)-d(b)|]/2
则最后一块骨牌倒下的时间为max{d(a),L(a,b)]
根据以上分析，我们可以先写出Dijkstra的求最短路的代码，然后插入求最后一块骨牌倒下时间的代码，就像下面的算法所做的那样：PROBLEM-Dominio-Effect()
1 input n, m
2 for a←1 to n
3 do for b←1 to n
4 do w[a][b]←+¥
5 for i←1 to m
6 do input a, b, t
7 w[a][b]←w[b][a]←t
8 lastA ← lastB ← 1
9 lastT ← 0
10 for i←1 to n
11 do d[i]←+¥
12 c[i]←FALSE
13 d[1]←0
14 for i←1 to n
15 do a←0
16 for b←1 to n
17 do if Øc[b] Ù (a=0 Ú d[a]>d[b])
18 then a←b
19 if d[a]>lastT
20 then lastT ← d[a]
21 lastA ← lastB ← a
22 for b←1 to n
23 do if d[a] + t[a][b] < d[b]
24 then d[b] ← d[a] + t[a][b]
25 else t←min(d[a],d[b])+(t[a][b] - | d[a]-d[b] | )/2
26 if c[b] Ù t>lastT
27 then lastT ← t
28 lastA ← min(a,b)
29 lastB ← max(a,b)
30 c[a]←TRUE
31 output “The last domino falls after “, lastT, “ seconds, “
32 if lastA = lastB
33 then output "at key domino ", lastA, “.¿”
34 else output "between key dominoes “, lastA, “ and “, lastB, “. ¿"
算法第1-7行输入数据并立刻转换为图，第8-30行是标准的Dijkstra算法，其中第19-21行和第25-29行不属于求最短路，而是求最后一块骨牌的倒下时间。