题目描述

现在有n个容器服务，服务的启动可能有一定的依赖性（有些服务启动没有依赖），其次，服务自身启动加载会消耗一些时间。

给你一个$n\times n$的二维矩阵useTime，其中useTime[i][i]=10表示服务i自身启动加载需要消耗10s，useTime[i][j]=1表示服务i启动依赖服务j启动完成，useTime[i][k]=0表示服务i启动不依赖服务k。其中o <= i, j, k < n。服务之间没有循环依赖（不会出现环），若想对任意一个服务i进行集成测试（服务i自身也需要加载），求最少需要等待多少时间。

输入描述

第一行输入服务总量n，之后的n行表示服务启动的依赖关系以及自身启动加载耗时，最后输入k表示计算需要等待多少时间后，可以对服务k进行集成测试，其中1 <= k <= n, 1 <= n <= 100。

输出描述

最少需要等待多少时间（单位：秒）后，可以对服务k进行集成测试。

示例描述

示例一

输入：

3
5 0 0
1 5 0
0 1 5
3

输出：

15

说明：
服务3启动依赖服务2，服务2启动依赖服务1，由于服务1、2、3自身加载都需要消耗5s，所以5+5+5=15s，需要等待15s后可以对服务3进行集成测试。

示例二

输入：

3
5 0 0
1 10 1
1 0 11
2

输出：

26

说明：
服务2启动依赖服务1和服务3，服务3启动需要依赖服务1，服务1、2、3自身加载需要消耗5s、10s、11s，所以5+10+11=26s，需要等待26s后可以对服务2进行集成测试。

示例三

输入：

4
2 0 0 0
0 3 0 0
1 1 4 0
1 1 1 5
4

输出：

12

说明：
服务3启动依赖服务1和服务2，服务4启动需要依赖服务1、2、3，服务1、2、3、4自身加载需要消耗2s、3s、4s、5s，所以3+4+5=12s（因为服务1和服务2可以同时启动），需要等待12s后可以对服务4进行集成测试。

示例四

输入：

5
1 0 0 0 0
0 2 0 0 0
1 1 3 0 0
1 1 0 4 0
0 0 1 1 5
5

输出：

11

说明：
服务3启动依赖服务1和服务2，服务4启动需要依赖服务1和服务2，服务5启动需要依赖服务3和服务4，服务1、2、3、4、5自身加载需要消耗1s、2s、3s、4s、5s，所以2+4+5=11s（因为服务1和服务2可以同时启动，服务3和服务4可以同时启动），需要等待11s后可以对服务5进行集成测试。

解题思路

1. 本题使用深度优先遍历DFS进行解题；
2. 调用深度优先遍历，返回总耗时
3. 深度优先遍历：
   1. 确认递归函数的参数：参数包括服务k、服务耗时矩阵arr。
   2. 终止条件：当查找不到启动依赖服务终止，返回耗时，并加上服务自身耗时。
   3. 处理：遍历服务，得到服务k启动依赖的服务。
   4. 递归遍历，计算下一层依赖服务的耗时，得到总最大服务耗时时间。
4. 返回服务总耗时时间。

解题代码

def dfs(arr, k):max_time = 0# 遍历服务for i in range(len(arr)):# 得到服务k启动依赖的服务if arr[k][i] != 0 and i != k:# 计算启动依赖服务的最大耗时，并记录到总耗时中max_time = max(max_time, dfs(arr, i))return max_time + arr[k][k]def solve_method(arr, k):total_time = dfs(arr, k - 1)return total_timeif __name__ == '__main__':k = 3useTime = [[5, 0, 0],[1, 5, 0],[0, 1, 5]]assert solve_method(useTime, k) == 15k = 2useTime = [[5, 0, 0],[1, 10, 1],[1, 0, 11]]assert solve_method(useTime, k) == 26k = 4useTime = [[2, 0, 0, 0],[0, 3, 0, 0],[1, 1, 4, 0],[1, 1, 1, 5],]assert solve_method(useTime, k) == 12k = 5useTime = [[1, 0, 0, 0, 0],[0, 2, 0, 0, 0],[1, 1, 3, 0, 0],[1, 1, 0, 4, 0],[0, 0, 1, 1, 5]]assert solve_method(useTime, k) == 11