题解 | #旅行Ⅰ#

# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param N int整型 N
# @param V int整型 V
# @param A int整型一维数组 A
# @param list Point类一维数组 List
# @return int整型
#
class Solution:
    def Travel(self , N , V , A , list ):
        # write code here
        # 构建限制graph
        graph = {i+1:[] for i in range(N)}
        for point in list:
            graph[point.x].append(point.y)

        def select_city(graph):
            """
            返回旅游顺序城市列表
            """
            in_degree = {u: 0 for u in graph.keys()}
            for u in graph.keys():
                for v in graph[u]:
                    in_degree[v] += 1
            
            degree_0_dict = {u: A[u-1] for u in graph if in_degree[u]==0}

            res = []
            while degree_0_dict:
                # degree_0按花费小的城市编号小的排序
                degree_0 = sorted(degree_0_dict.items(), key=lambda x: (x[1], x[0]))
                out = degree_0.pop(0)
                degree_0_dict.pop(out[0])
                res.append(out)
                # 对后置节点的度-1
                for v in graph[out[0]]:
                    in_degree[v] -= 1
                    if in_degree[v] == 0:
                        degree_0_dict[v] = A[v-1]
            return res

        cnt = 0
        rest_money = V
        res = select_city(graph)
        while rest_money > 0 and res:    
            rest_money -= res[0][1]
            cnt += 1
            res.pop(0)
        return cnt