样例输入
4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2
样例输出
4

思路：
$T_{max}=max(T_h)$表示$T_{max}$由单层最大消耗时间$max(T_h)$决定,
而$max(T_h)$又由该深度权值最大的一条边$max(t_{h,j})$决定，所以可以理解为$T_{max}$由最生成树中最大边权值决定。用prim跑一遍最小生成树求出最大边权即可。

代码:

from collections import defaultdict
from heapq import *


def prim(begin_point, edges):
    # type nodes :int
    # type edges:[[begin node,end node,weights]]
    # rtype [(begin node,end node,weights)],max(cost)
    conn = defaultdict(list)
    for n1, n2, c in edges:
        conn[n1].append((c, n1, n2))
        conn[n2].append((c, n2, n1))

    mst = []
    used = set()
    used = {begin_point}
    usable_edges = conn[begin_point][:]
    heapify(usable_edges) 
    maxcost = 0
    while usable_edges:
        cost, n1, n2 = heappop(usable_edges)
        if n2 not in used:
            used.add(n2)
            mst.append((n1, n2, cost))
            maxcost = max(cost, maxcost)
            for e in conn[n2]:
                if e[2] not in used:
                    heappush(usable_edges, e)
    return mst, maxcost

n = int(input().strip())
m = int(input().strip())
root = int(input().strip())
edges = []
for i in range(m):
    edges.append((map(int, input().split())))
mst, max_cost = prim(root, edges)
print(max_cost)

提交:

注:
python还是很卡时间的，用c应该好些。