import copy


def takesecond(elem):
    return elem[1]


# 计算两地之间的距离
def get_distance_city(point_position, index, logistics_center_position=None):
    distance = []
    if logistics_center_position == None:
        center_point_x = point_position[index - 1][0]
        center_point_y = point_position[index - 1][1]
        for i in range(len(point_position)):
            if i == index - 1:
                continue
            center_point_to_other_point = ((center_point_x - point_position[i][0]) ** 2 + (
                center_point_y - point_position[i][1]) ** 2) ** (1/2)
            str_index_format = '{0}->{1}'.format(index, i + 1)
            format_distance = (str_index_format, center_point_to_other_point)
            distance.append(format_distance)
    else:
        for i in range(len(point_position)):
            logistics_center_point_to_city = ((logistics_center_position[0] - point_position[i][0]) ** 2 + (
                logistics_center_position[1] - point_position[i][1]) ** 2) ** (1/2)
            str_index_format = '0->{0}'.format(i + 1)
            format_distance = (
                str_index_format, logistics_center_point_to_city)
            distance.append(format_distance)
    return distance

# 按两地之间的距离进行排序


def sort_all_distance_by_elem_1(distance):
    distance.sort(key=takesecond)
    return distance


if __name__ == "__main__":
    # 初始化城市坐标
    points_position = [[12.8, 8.5], [18.4, 3.4], [15.4, 16.6], [18.9, 15.2], [15.5, 11.6], [3.9, 10.6], [10.6, 7.6], [8.6, 8.4], [12.5, 2.1], [
        13.8, 5.2], [6.7, 16.9], [14.8, 2.6], [1.8, 8.7], [17.1, 11], [7.4, 1],  [0.2, 2.8], [11.9, 19.8], [13.2, 15.1], [6.4, 5.6], [9.6, 14.8]]
    # 初始化各个城市需求量
    cities_need_goods = [0.1, 0.4, 1.2, 1.5, 0.8, 1.3, 1.7, 0.6,
                         1.2, 0.4, 0.9, 1.3, 1.3, 1.9, 1.7, 1.1, 1.5, 1.6, 1.7, 1.5]
    cities_distance = []
    # 获得城市之间的距离
    for i in range(1, 21):
        cities_distance.append(get_distance_city(points_position, i))
    # 定义物流中心的坐标
    logistics_center_position = [14.2, 13.1]
    logistics_center_to_cities_distance = get_distance_city(
        points_position, 0, logistics_center_position)
    not_sort_logistics_center_to_cities_distance = copy.deepcopy(
        logistics_center_to_cities_distance)
    # 初始化城市的到达标记
    cities_flag = [0 for i in range(20)]
    # 对城市之间的距离以及物流中心到城市的距离进行排序
    for city_index in range(20):
        cities_distance[city_index] = sort_all_distance_by_elem_1(
            cities_distance[city_index])
    logistics_center_to_cities_distance = sort_all_distance_by_elem_1(
        logistics_center_to_cities_distance)
    # print(logistics_center_to_cities_distance)
    # print(not_sort_logistics_center_to_cities_distance[2][1])
    # 初始化总路程
    bound = 0
    # 初始化用到货车的数量
    number_of_car = 0
    # 初始化行驶路线
    path = []
    for i in range(20):
        # 找到离物流中心最近的城市进行配送
        to_city = int(logistics_center_to_cities_distance[i][0].split('->')[1])
        current_capacity = 0
        distance_bound = 0
        m = 0
        # 判断该城市是否已经配送完成
        if cities_flag[to_city - 1] == 0:
            path.append('new car')
            path.append(to_city)
            number_of_car += 1
            cities_flag[to_city - 1] = 1
            distance_bound += logistics_center_to_cities_distance[i][1]
            current_capacity += cities_need_goods[to_city - 1]
            # 车辆基于当前的配送城市继续进行配送
            while True:
                if sum(cities_flag) == 20:
                    distance_bound += not_sort_logistics_center_to_cities_distance[path[len(
                        path) - 1] - 1][1]
                    bound += distance_bound
                    break
                prev_city = to_city
                temp = cities_distance[to_city - 1][m][1]
                to_city = int(
                    cities_distance[to_city - 1][m][0].split('->')[1])
                if cities_flag[to_city - 1] == 0:
                    cities_flag[to_city - 1] = 1
                    path.append(to_city)
                    return_logistice_center_distance = not_sort_logistics_center_to_cities_distance[
                        to_city - 1][1]
                    # 判断是否满足继续配送的条件
                    # 条件1：当前货车已经行驶的路程+将要行驶至下一城市的路程+返回物流中心的路程是否超过50km
                    # 条件2：汽车剩余的配送货物是否能满足下一城市的需求量
                    if distance_bound + temp + return_logistice_center_distance <= 50 and current_capacity + cities_need_goods[to_city - 1] <= 8:
                        distance_bound += temp
                        current_capacity += cities_need_goods[to_city - 1]
                        m = 0
                    else:
                        cities_flag[to_city - 1] = 0
                        path.pop()
                        return_distance = not_sort_logistics_center_to_cities_distance[path[len(
                            path) - 1] - 1][1]
                        distance_bound += return_distance
                        bound += distance_bound
                        break
                else:
                    m += 1
                    to_city = prev_city
        if sum(cities_flag) == 20:
            break
    print('得到的路径长度为: {0}'.format(bound))
    print('得到的这条最短路径为: {0}'.format(path))
    print('需要的车辆个数为: {0}'.format(number_of_car))