题意 ： 一个新的多米诺骨牌游戏，就是这个多米诺骨中有许多关键牌，他们之间由一行普通的骨牌相连接，当一张关键牌倒下的时候，连接这个关键牌的每一行都会倒下，当倒下的行到达没有倒下的关键牌时，这个关键牌也会倒下，然后与这个关键牌相连接的所有行都会倒下，每一行有两个端点也就是两个关键牌，可以从任意一个端点开始倒下，也可以从两个端点同时开始倒下，从第一张骨牌开始倒，最后倒下的牌的位置以及时间。
思路 : 先利用Dijkstra求出每张关键牌倒下的时间time[i],即求出第一张关键牌到其他关键牌的最短路径，然后求出众最短路径中最大的那个，即为time1。再计算每一行倒下的时间，每一行的两个关键牌的位置设为i,j,则这一行倒下的时间为（time[i]+time[j]+Edge[i][j]）/2.0，找到最大值即为time2。求出time1，time2的最大值，即为我们所求。
因为最后那个%.1lf的问题还错了一遍，交C++即可。
//Domino Effect
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm> using namespace std ; const int INF = ;
const int maxn = ;
int n, m;
int Edge[maxn][maxn] ;
bool vis[maxn] ;
int timee[maxn] ; void dijkstra()
{
for(int i = ; i <= n ; i++)
{
timee[i] = Edge[][i] ;
vis[i] = false ;
}
timee[] = ;
vis[] = true ;
for(int i = ; i < n ; i++)
{
int minn = INF , u = ;
for(int j = ; j <= n ; j++)
{
if(!vis[j] && timee[j] < minn)
{
u = j ;
minn = timee[j] ;
}
}
vis[u] = true ;
for(int k = ; k <= n ; k++)
{
if(!vis[k] && Edge[u][k] < INF && timee[u] + Edge[u][k] < timee[k])
timee[k] = timee[u] + Edge[u][k] ;
}
}
double time1 = -999999999.0 ;
int flag ;
for(int i = ; i <= n ; i++)
{
if(timee[i] > time1)
time1 = timee[i],flag = i ;
}
double time2 = -9999999999.0 ;
int pos1,pos2 ;
for(int i = ; i <= n ; i++)
{
for(int j = ; j <= n ; j++)
{
double temp = (timee[i] + timee[j] + Edge[i][j])/2.0 ;
if(Edge[i][j] < INF && temp > time2)
{
time2 = temp ;
pos1 = i ;
pos2 = j ;
}
}
}
if(time1 < time2)
printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n\n",time2,pos1,pos2) ;
else
printf("The last domino falls after %.1lf seconds, at key domino %d.\n\n",time1,flag) ;
}
int main()
{
int cas = ;
while(~scanf("%d %d",&n,&m))
{
if(n == && m == )
break ;
int u,v ,w ;
for(int i = ; i <= n ; i++)
for(int j = ; j <= n ; j++)
Edge[i][j] = INF ;
for(int i = ; i < m ; i++)
{
scanf("%d %d %d",&u,&v,&w) ;
Edge[u][v] = w ;
Edge[v][u] = w ;
}
printf("System #%d\n",cas++) ;
dijkstra() ;
}
return ;
}