题解 | #旅行Ⅰ#

除了上面的条件还有一个条件是：

她每次会选择当前能去的花费最小的城市,如有多个花费一样的则首先去编号小的城市

所以先写一个函数（nextCity）可以实现目前可以去的城市里面花费最小且编号小的城市（ps 真抠。）

初始化如下两个数组：

• 数组city_can表示城市是否可以去

0表示可以去，-1表示已经去过，大于0表示前置未去的城市数 ）

• 二维数组方便查询前置城市 city_limit

city_limit[x][y] == 1 表示 x为y的前置城市 ，值为0的时候表示不是前置城市)

然后就用nextCity函数查询下一个可以去的城市，且花费不超预算。

如果超预算就终止循环，因为当前city的花费已经是最少的，后面也不可能有其他城市花费满足预算需求了。

不超预算的话就去，将后置城市的数值-1，将自身置为-1

# 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 getNextCity(self,city,cost,city_can):
        #TODO 按照花费排序
        # 找出city_can 里面为0 的city cost最少且编号最小
        min_cost = -1
        city_id = -1
        for i in city :
            if min_cost == -1 or min_cost > cost[i] :
                if city_can[i] == 0 :
                    city_id = i
                    min_cost = cost[i]
            
        return city_id
    
    
    def Travel(self , N , V , A , list ):
        city = [i for i in range(N)]
        city_can = [0 for i in range(N)]
        city_limit = [ [0 for n in range(N)] for i in range(N)]
        
        for p in list :
            city_limit[p.x-1][p.y-1] = 1
            city_can[p.y-1] += 1
        
        city_visit_num = 0
        city_id = self.getNextCity(city,A,city_can)
        
        while city_id > -1 :
            if V < A[city_id] :
                break
            V = V - A[city_id]
            city_visit_num += 1 
            city_can[city_id] = -1
            for m in range(N):
                if city_limit[city_id][m] > 0 :
                    city_limit[city_id][m] = 0
                    city_can[m] -= 1
                    
            city_id = self.getNextCity(city,A,city_can)
        # write code here
        return city_visit_num