1
 2
 3
 4
 5
 6
 7
 8
 9
10

__all__ = (
    'Field', 'CharField', 'IntegerField',
    'DateField', 'TimeField', 'DateTimeField', 'DurationField',
    'RegexField', 'EmailField', 'FileField', 'ImageField', 'URLField',
    'BooleanField', 'NullBooleanField', 'ChoiceField', 'MultipleChoiceField',
    'ComboField', 'MultiValueField', 'FloatField', 'DecimalField',
    'SplitDateTimeField', 'GenericIPAddressField', 'FilePathField',
    'JSONField', 'SlugField', 'TypedChoiceField', 'TypedMultipleChoiceField',
    'UUIDField',
)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# -*- coding:utf-8 -*-

if __name__ == '__main__':
    # n 树中节点个数
    # m 非叶子节点个数
    n, m = list(map(int, input().strip().split(' ')))
    # 二维数组
    # 元素的下标表示节点的 ID
    # 第 1 个元素不使用
    tree = [[] for _ in range(n+1)]
    while m != 0:
        tokens = list(map(int, input().split(' ')))
        _id = tokens[0]
        children = tokens[2:]
        tree[_id] = children
        m = m - 1

    # 记录每一层叶子节点的数量
    counts = [0 for _ in range(n+1)]
    # 记录最大深度
    max_depth = 0

    def dfs(i, depth):
        global max_depth, counts, tree

        if len(tree[i]) == 0:  # 节点 i 为叶子节点
            counts[depth] = counts[depth] + 1
            max_depth = max(depth, max_depth)
            return
        for j in tree[i]:
            dfs(j, depth + 1)

    dfs(1, 0)

    print(' '.join([str(count) for count in counts[:max_depth+1]]))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

# -*- coding:utf-8 -*-
import sys

MAX_INT = sys.maxsize

if __name__ == '__main__':
    # m 城市个数
    # n 路径条数
    # start 起始城市下标
    # end 结束城市下标
    m, n, start, end = map(int, input().strip().split(' '))
    # nums_of_teams 各城市救援队的数量
    nums_of_teams = list(map(int, input().strip().split(' ')))

    assert m == len(nums_of_teams)

    # 城市间的路径矩阵
    roadmap = [
        [MAX_INT for _ in range(m)] for _ in range(m)
    ]
    # 根据输入初始化 roadmap
    while n != 0:
        i, j, d = map(int, input().strip().split(' '))
        roadmap[i][j] = d
        roadmap[j][i] = d  # 对角矩阵表示无向图
        n = n - 1

    roadmap[start][start] = 0  # 测试点中的起始城市和结束城市可能相同

    # 起始城市到其余城市最短路径条数
    nums_of_short_paths = [0 for _ in range(m)]
    # 保存访问记录, 0 表示未访问, 1 表示已访问
    visited = [0 for _ in range(m)]
    # 起始城市到其余城市最短路径
    dists = [MAX_INT for _ in range(m)]
    # 起始城市到其余城市在最短路径的基础上, 各路径上城市救援队个数的和
    weights = [0 for _ in range(m)]

    # 初始状态
    nums_of_short_paths[start] = 1  # 起始城市到自己, 表示有 1 条
    dists[start] = 0
    weights[start] = nums_of_teams[start]

    for i in range(m):
        u = -1
        min_d = MAX_INT
        # 在剩余未访问的城市中, 找到距离起始城市最近的城市
        for j in range(m):
            if visited[j] == 0 and dists[j] < min_d:
                min_d = dists[j]
                u = j
        if u == -1:
            break

        visited[u] = 1  # 第 1 次找到的必然是起始城市
        for k in range(m):
            # for 循环用于计算：
            # > 已访问城市到未访问城市的最短路径之和
            if visited[k] == 0 and roadmap[u][k] != MAX_INT:
                # 已访问城市与未访问城市之间必须具有连通性
                if dists[u] + roadmap[u][k] < dists[k]:
                    dists[k] = dists[u] + roadmap[u][k]
                    nums_of_short_paths[k] = nums_of_short_paths[u]
                    weights[k] = weights[u] + nums_of_teams[k]
                elif dists[u] + roadmap[u][k] == dists[k]:
                    nums_of_short_paths[k] = nums_of_short_paths[k] + nums_of_short_paths[u]
                    if nums_of_teams[k] + weights[u] > weights[k]:
                        weights[k] = weights[u] + nums_of_teams[k]

    print(f'{nums_of_short_paths[end]} {weights[end]}', end='')