题意

有m排放置好的多米诺骨牌，每排的头尾骨牌称为“关键骨牌”，共有n个关键骨牌，每排多米诺倒下需要L秒，关键骨牌倒下的时间忽略不计。推倒关键骨牌1，求最后一个骨牌倒下的时间及位置。（若最后一个倒下的骨牌不是关键骨牌，则按升序输出这个骨牌所在的那一排的两端的关键骨牌）

样例输入

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算法求出从关键骨牌1到各个关键骨牌的最短路径（即最短耗时）。而与最短路径不相干的边倒下的时刻，则是关键骨牌1到这条边两端的关键骨牌所需的最短时间之和，再加上这条边倒下所需的时间，再除以2。（理解这一点是这道题的关键，类似与相遇问题）最后，只要比较关键骨牌1到某个关键骨牌的最短路径耗时 和 某条边的倒下的时刻，取两者中较大的一方，即可得出结论。

注意点

由于关键骨牌倒下时间忽略不计，所以当输入数据只有1个骨牌时，耗时为0.0，倒下的关键骨牌为1本身。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6  7 const int N = 510, INF = 0x3f3f3f3f; 8 int graph[N][N]; 9 10 void SPFA(int n)11 {12     queue
         
           q;13     bool vis[N] = {
   0};14     vis[0] = true;15     int D[N];16     for(int i=0; i
          
            Max1)48 Max1 = D[i], tag1 = i;49 for(int i=0; i
           
             Max2)56 Max2 = sum, tag21 = i, tag22 = j;57 }58 }59 double ans = (double)Max2 / 2;60 if(ans <= (double)Max1)61 printf("The last domino falls after %.1lf seconds, at key domino %d.\n\n", (double)Max1, tag1+1);62 else63 printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n\n", ans, tag21+1, tag22+1);64 return ;65 }66 67 int main(void)68 {69 int n, m, u, v, w;70 for(int t=0; scanf("%d %d", &n, &m), n+m; )71 {72 memset(graph, INF, sizeof(graph));73 for(int i=0; i
           
          
         
        
       
      
     

测试数据

2 11 2 273 31 2 51 3 52 3 51 05 7   1 2 11 3 21 4 31 5 52 3 13 4 14 5 14 51 2 31 3 31 4 53 4 22 3 93 31 3 11 2 32 3 30 0

System #1The last domino falls after 27.0 seconds, at key domino 2.System #2The last domino falls after 7.5 seconds, between key dominoes 2 and 3.System #3The last domino falls after 0.0 seconds, at key domino 1.System #4The last domino falls after 4.5 seconds, between key dominoes 1 and 5.System #5The last domino falls after 7.5 seconds, between key dominoes 2 and 3.System #6The last domino falls after 3.5 seconds, between key dominoes 2 and 3.