題目描述：
你知道多米諾骨牌除了用來玩多米諾骨牌游戲外，還有其他用途嗎？多米諾骨牌游戲：取一
些多米諾骨牌，豎著排成連續的一行，兩張骨牌之間只有很短的空隙。如果排列得很好，當你推
倒第1 張骨牌，會使其他骨牌連續地倒下（這就是短語“多米諾效應”的由來）。
然而當骨牌數量很少時，這種玩法就沒多大意思了，所以一些人在80 年代早期開創了另一個
極端的多米諾骨牌游戲：用上百萬張不同顏色、不同材料的骨牌拼成一幅復雜的圖案。他們開創
了一種流行的藝術。在這種骨牌游戲中，通常有多行骨牌同時倒下。
你的任務是編寫程序，給定這樣的多米諾骨牌游戲，計算最後倒下的是哪一張骨牌、在什麼
時間倒下。這些多米諾骨牌游戲包含一些“關鍵牌”，他們之間由一行普通骨牌連接。當一張關鍵
牌倒下時，連接這張關鍵牌的所有行都開始倒下。當倒下的行到達其他還沒倒下的關鍵骨牌時，
則這些關鍵骨牌也開始倒下，同樣也使得連接到它的所有行開始倒下。每一行骨牌可以從兩個端
點中的任何一張關鍵牌開始倒下，甚至兩個端點的關鍵牌都可以分別倒下，在這種情形下，該行
最後倒下的骨牌為中間的某張骨牌。假定骨牌倒下的速度一致。
輸入描述：
輸入文件包含多個測試數據，每個測試數據描述了一個多米諾骨牌游戲。每個測試數據的第
1 行為兩個整數：n 和m，n 表示關鍵牌的數目，1≤n<500；m 表示這n 張牌之間用m 行普通骨
牌連接。n 張關鍵牌的編號為1～n。每兩張關鍵牌之間至多有一行普通牌，並且多米諾骨牌圖案
是連通的，也就是說從一張骨牌可以通過一系列的行連接到其他每張骨牌。
接下來有m 行，每行為3 個整數：a、b 和t，表示第a 張關鍵牌和第b 張關鍵牌之間有一行
普通牌連接，這一行從一端倒向另一端需要t 秒。每個多米諾骨牌游戲都是從推倒第1 張關鍵牌
開始的。
輸入文件最後一行為n = m = 0，表示輸入結束。
輸出描述：
對輸入文件中的每個測試數據，首先輸出一行"System #k"，其中k 為測試數據的序號；然後
再輸出一行，首先是最後一塊骨牌倒下的時間，精確到小數點後一位有效數字，然後是最後倒下
骨牌的位置，這張最後倒下的骨牌要麼是關鍵牌，要麼是兩張關鍵牌之間的某張普通牌。輸出格
式如樣例輸出所示。如果存在多個解，則輸出任意一個。每個測試數據的輸出之後輸出一個空行。
樣例輸入：
2 1
1 2 27
3 3
1 2 5
1 3 5
2 3 5
0 0
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.
算是模版Dijkstra題目了,多了判斷哪種最優解的情況。
a) 先計算每一張關鍵牌倒下的dist[i]。這需要利用Dijkstra 算法求第1 張關鍵牌到其他每
張關鍵牌的最短路徑。然後取dist[i]的最大值，設為max1。
b) 計算每一行完全倒下的時間。設每一行的兩端的關鍵牌為i 和j，則這一行完全倒下的時
間為(dist[i] + dist[j] +
edge[i][j])/2.0，其中edge[i][j]為連接第i、j 兩張關鍵牌的行倒下
所花的時間。取所有行完全倒下時間的最大值，設為max2。
c) 如果max2 > max1，則是第②種情形；否則是第①種情形。
[cpp]
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#define MAX 600
#define INF 0x7FFFFFFF
# define eps 1e-5
using namespace std;
int n,m;
int edge[MAX][MAX],visit[MAX],dist[MAX];//邊的信息，訪問，最短距離
void dijkstra(int u0)
{
int i,j,v;
for(i=1; i<=n; i++)//初始化
{
dist[i] = edge[u0][i];
}
visit[u0] = 1;
for(j=0; j<n-1; j++)
{
int min = INF;
for(i=1; i<=n; i++)
{
if(!visit[i] && min > dist[i])
{
min = dist[i];
v = i;
}
}
visit[v] = 1;//點v與源點同一集合
for(i=1; i<=n; i++)//隨著新的頂點加入，更新dist值
{
if(!visit[i] && edge[v][i] < INF && edge[v][i] + dist[v] < dist[i])
dist[i] = edge[v][i] + dist[v];
}
}
}
int main()
{
int i,j,a,b,c,tt = 1;
while(scanf("%d%d",&n,&m))
{
if(n==0 && m==0)
break;
for(i=1; i<=n; i++)//初始化
for(j=1; j<=n; j++)
{
if(i == j)
edge[i][j] = 0;
else
edge[i][j] = INF;
}
for(i=0; i<m; i++)//構圖
{
scanf("%d%d%d",&a,&b,&c);
edge[a][b] = c;
edge[b][a] = c;
}
memset(visit,0,sizeof(visit));
dijkstra(1);//求出1到所有定點最短路
double max1 = -10000000;
int index;
for(i=1; i<=n; i++)//情況a
{
if(max1 < dist[i])
{
max1 = dist[i]*1.0;
index = i;
}
}
double max2 = -10000000;
int index1,index2;
for(i=1; i<=n; i++)//情況b
for(j=1; j<=n; j++)
{
if(edge[i][j] != INF && i < j)//i < j 算是優化，有了它就是0ms，沒有就是16ms
{
if(max2 < (dist[i]+dist[j]+edge[i][j])/2.0)
{
max2 = (dist[i]+dist[j]+edge[i][j])/2.0;
index1 = i;
index2 = j;
}
}
}
printf("System #%d\n",tt++);
if(max1 >= max2)//選出符合的情況
printf("The last domino falls after %.1f seconds, at key domino %d.\n",max1,index);
else
printf("The last domino falls after %.1f seconds, between key dominoes %d and %d.\n",max2,index1,index2);
printf("\n");
}
return 0;
}
