P3753. 微服务的集成测试

解题思路

本题在常规的拓扑排序问题上加多了启动时间这一个限制条件，属于变形题。

构建邻接表和入度表

构建邻接表和入度表比较常规，直接根据关联矩阵的特点进行构建即可。

搜索入度为0的节点

接着我们搜索所有入度为0的节点，存入队列中，作为整个拓扑循环的若干起点。

不考虑时间依赖的拓扑循环模板

如果不考虑时间依赖的问题，本题的拓扑循环可以直接套用模板：

记录时间信息

由于在本题中，节点之间的依赖存在时间上的差别，我们需要记录两个东西：

• 储存每一个节点加载自身所需要的时间
• 储存每一个节点启动需要花费的总时间

考虑时间依赖的拓扑循环

然后我们需要考虑两件事：

1. 每一个节点的启动时刻（注意此处尚未考虑节点自身启动所花费的时间），依赖于其所有前置节点中启动得最晚的那一个。 2. 每一个节点启动时还需要加上自身加载的时间，才是这个节点启动完毕的时刻。

所以对于整个拓扑循环过程，我们多加上两行代码即可：

输出结果

最终输出节点k的启动完毕时刻：

复杂度分析 设微服务个数为 n。读入 n×n 的 useTime 矩阵并用双重循环把它转成邻接表和入度数组，这一步固定要扫描全部 n^2 个矩阵元素，是 O(n^2)，也是整个算法的瓶颈。设依赖关系（边）数为 E（E 不超过 n^2），拓扑排序 BFS 中每个节点至多入队一次、每条边使入度减一并做一次 max 转移，为 O(n + E)，被 O(n^2) 覆盖。总时间复杂度 O(n^2)。空间上，矩阵本身占 O(n^2)，邻接表为 O(n + E)，loadTimeList、totalTime、入度数组和队列均为 O(n)，空间复杂度由输入矩阵主导，为 O(n^2)。

边界与注意事项

• 查询的服务编号从 1 开始，而代码内部索引从 0 开始，读入后要做减一处理（例如服务 4 对应代码中的节点 3），漏掉会查错节点。
• 矩阵对角线 useTime[i][i] 表示服务自身的加载时间而不是依赖关系，构建邻接表时用 i != j 把它排除，并单独存进 loadTimeList。
• 没有任何依赖的服务入度为 0，直接进入初始队列；若查询的服务本身无依赖，答案就是它自身的加载时间。
• totalTime[nxt] 用 max 更新，因为一个服务必须等它所有前置中「最晚启动完成」的那个结束后才能开始加载。
• 题目保证依赖关系无环，所以代码不需要做环检测；弹出节点恰好是查询节点 k 时提前 break 只是提前结束的优化，注释说明不加也不影响正确性。