题意分析

本题描述了多米诺骨牌系统，该系统由若干关键多米诺骨牌和连接它们的普通多米诺骨牌排组成。当推倒编号为 1 的关键多米诺骨牌时，与之相连的排会倒下，进而引发其他关键多米诺骨牌倒下。多米诺骨牌排可以从两端同时倒下，且以均匀速度倒下。任务是编写程序，对于给定的多米诺骨牌系统，计算最后一块多米诺骨牌倒下的时间和位置（可能在关键多米诺骨牌处，也可能在两个关键多米诺骨牌之间）。

解题思路

本题可通过 Dijkstra 算法计算从编号为 1 的关键多米诺骨牌到其他所有关键多米诺骨牌的最短路径，然后分两种情况讨论最后一块多米诺骨牌倒下的时间和位置：

1. 最后一块骨牌在关键多米诺骨牌处倒下：找到距离编号为 1 的关键多米诺骨牌最远的关键多米诺骨牌，其距离即为这种情况下最后一块骨牌倒下的时间。
2. 最后一块骨牌在两个关键多米诺骨牌之间倒下：对于每一对相邻的关键多米诺骨牌，计算它们之间排的中间位置倒下的时间，取最大值。

代码实现步骤

1. 输入处理：
   • 读取关键多米诺骨牌的数量 n 和它们之间排的数量 m。
   • 初始化邻接矩阵 e 存储骨牌之间的距离，若两点不相邻则距离为 MAXN，自身到自身距离为 0。
   • 读取每对相邻骨牌之间的距离，更新邻接矩阵。
2. Dijkstra 算法求最短路径：
   • 初始化距离数组 dis 存储从编号为 1 的骨牌到其他骨牌的距离，标记数组 book 标记骨牌是否已确定最短距离。
   • 从编号为 1 的骨牌开始，每次选择距离源点最近且未确定最短距离的骨牌，更新其相邻骨牌的距离。
3. 计算最后一块骨牌倒下的时间和位置：
   • 情况一：遍历距离数组 dis，找到距离最大的关键多米诺骨牌，记录其编号和距离。
   • 情况二：遍历邻接矩阵 e，对于每对相邻的骨牌，计算它们之间排的中间位置倒下的时间，取最大值。
4. 输出结果：
   • 输出用例编号。
   • 比较两种情况下的时间，输出最后一块骨牌倒下的时间和位置。
   • 输出一个空行分隔不同用例的输出。

复杂度分析

• 时间复杂度：Dijkstra 算法的时间复杂度为 $O(n^2)$，后续计算最后一块骨牌倒下时间和位置的时间复杂度也为 $O(n^2)$，因此总的时间复杂度为 $O(n^2)$。
• 空间复杂度：主要使用了邻接矩阵 e、距离数组 dis 和标记数组 book，空间复杂度为 $O(n^2)$。

代码解释

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<list>
#include<queue>
#define mm(a,b) memset(a,b,sizeof(a))
#define ACCELERATE (ios::sync_with_stdio(false),cin.tie(0))
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define MAXN 0x3f3f3f3f3f3f3f3f
#define PI acos(-1.0)
#define E exp(1.0)
using namespace std;

//#define debug

const int N = 505;

int main()
{
    #ifdef debug
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    #endif // debug

    int e[N][N];  // 邻接矩阵，存储骨牌之间的距离
    int dis[N];   // 距离数组，存储从编号为 1 的骨牌到其他骨牌的距离
    bool book[N]; // 标记数组，标记骨牌是否已确定最短距离
    int n, m;
    int casei = 1;
    while (scanf("%d%d", &n, &m) != EOF && (n || m)) {
        // 初始化邻接矩阵
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j) e[i][j] = MAXN;
                else e[i][j] = 0;
            }
        }
        int u, v, w;
        // 读取每对相邻骨牌之间的距离，更新邻接矩阵
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            e[u][v] = w;
            e[v][u] = w;
        }
        // 初始化距离数组
        for (int i = 1; i <= n; i++) {
            dis[i] = e[1][i];
        }
        // 初始化标记数组
        mm(book, 0);
        book[1] = 1;
        // Dijkstra 算法求最短路径
        for (int i = 1; i <= n - 1; i++) {
            int mini = MAXN, f;
            for (int j = 1; j <= n; j++) {
                if (!book[j] && dis[j] < mini) {
                    mini = dis[j];
                    f = j;
                }
            }
            book[f] = 1;
            for (int k = 1; k <= n; k++) {
                if (e[f][k] < MAXN) {
                    if (dis[k] > dis[f] + e[f][k]) {
                        dis[k] = dis[f] + e[f][k];
                    }
                }
            }
        }
        double t1 = -1;  // 情况一：最后一块骨牌在关键多米诺骨牌处倒下的时间
        double t2 = -1;  // 情况二：最后一块骨牌在两个关键多米诺骨牌之间倒下的时间
        int x, x1, x2;
        // 情况一：找到距离编号为 1 的骨牌最远的关键多米诺骨牌
        for (int i = 1; i <= n; i++) {
            if (t1 < dis[i]) {
                t1 = dis[i] * 1.0;
                x = i;
            }
        }
        // 情况二：计算每对相邻骨牌之间排的中间位置倒下的时间
        for (int i = 1; i <= n - 1; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (e[i][j] != (int)MAXN) {
                    double q = (dis[i] + dis[j] + e[i][j]) / 2.0;
                    if (q > t2) {
                        t2 = q;
                        x1 = i;
                        x2 = j;
                    }
                }
            }
        }

        printf("System #%d\n", casei++);
        if (t1 < t2) {
            printf("The last domino falls after %.1f seconds, between key dominoes %d and %d.\n", t2, x1, x2);
        } else {
            printf("The last domino falls after %.1f seconds, at key domino %d.\n", t1, x);
        }
        printf("\n");
    }
    return 0;
}