初学模拟蚁群，自己的编译器上把迭代次数和蚂蚁数量调得很大，第五个测试点也是稳定的132而不是130，猜测陷入局部最优，求大佬改进

#模拟蚁群算法的python实现

#假设解决旅行商问题

import random

#创造地图
class City :
    def __init__(self , id ) :
        #城市的编号
        self.id = id
        #字典，记录到每个点的距离，初始为空
        self.distance = {}
        #字典，记录到每个城市路径的初始信息素浓度
        self.way_infor = {}

    #增加一条边
    def add_point ( self , to_id , far , init_infor_value ) :
        self.distance[to_id] = far
        #初始化到to的信息素浓度
        self.way_infor[to_id] = init_infor_value

    #查询到某地的距离
    def get_distance ( self , destination_id ) :
        return self.distance[destination_id]

    #查询到某地的路径的信息素浓度
    def get_infor_value ( self , to_id ) :
        return self.way_infor[to_id]

    #增加一条路径上的信息素浓度
    #p为信息素挥发率
    def add_infor ( self , to_id , infor_value  ) :
        #增加
        self.way_infor[to_id] = self.way_infor[to_id] + infor_value



#创造蚂蚁类
class Ant :
    def __init__(self, start, n):
        # 记录蚂蚁目前、最新到达的点，初始为给定的一个起点
        # start是一个City类
        self.start = start
        # 记录蚂蚁移动的路径，初始为0
        self.way = 0
        # 初始化一个字典，下标1<= i <= n ,初始值为0，表示都没访问过
        self.city_dic = {i: 0 for i in range(1, n + 1, 1)}
        #将起点标记成已访问
        self.city_dic[start.id] = 1
        #记录经过的所有城市的编号
        self.went_list = []
        self.went_list.append(start.id)
        #存储基础的信息素
        self.carry_infor = 0

    # 访问一个城市
    # 注意，需要输入一个城市编号，而不是城市类
    def __visited(self, city_id):
        self.city_dic[city_id] = 1

    # 查询一个节点是不是已经访问过了
    def __is_visited_or_not(self, city_id):
        if self.city_dic[city_id] == 1:
            return 1
        return 0

    # 记录是不是每个节点都访问了，是的话返回1，即TRUE，否则返回0，即FALSE
    def __all_visited(self):
        for city_id in self.city_dic:
            if self.city_dic[city_id] == 0:
                return 0
        return 1

    #到一个城市
    #to是一个city类
    def go_to ( self , to ) :
        #增加蚂蚁走过的距离
        self.way = self.way + self.start.get_distance( to.id )
        #更新起点
        self.start = to
        #标记为已走过
        self.__visited( to.id )
        #加入走过的路径
        self.went_list.append( to.id )

    #根据信息素浓度和能见度，随机决定走哪一条路
    #k1是信息素浓度参数，k2是能见度参数
    #init_start记录最开始的出发地的城市编号
    #返回要走的那个路的编号
    def choose ( self , k1 , k2 , init_start ) :

        #先找到所有可以到达的目的地
        to_ids = []
        #遍历从start出发能到达的所有节点
        #destination是City.id，是城市编号，是一个值
        for destination in self.start.distance :
            #能到达起点，并且所有节点都走到了
            if (destination == init_start) and (self.__all_visited() == 1) :
                self.way = self.way + self.start.get_distance ( init_start )
                #返回-1,表示已经到达目标了
                return -1
            #正常情况，走过的节点就不走
            #没走过的才走
            if self.__is_visited_or_not( destination ) == 0 :
                #没走过，加入可能走的路径
                to_ids.append(destination)
        #如果只有一条路，后面就不用讨论了
        #返回对应的编号
        if len(to_ids) == 1 :
            return to_ids[0]
        #不止一个
        #遍历所有能走的路，计算其概率权重
        #字典，存储概率权重
        p_dic = {}
        #记录概率权重总和
        p_sum = 0
        for to_id in to_ids :
            #获取信息素浓度
            information = self.start.get_infor_value (  to_id )
            #获取能见度，即距离的倒数
            nengjiandu = 1 / self.start.get_distance( to_id )
            p_dic[to_id] = ( information ** k1 ) * ( nengjiandu ** k2 )
            p_sum += p_dic[to_id]

        #计算每个点的概率
        l = []
        k = random.random()
        for to_id in to_ids :
            lx = []
            lx.append(to_id)
            lx.append( p_dic[to_id] / p_sum )
            l.append(lx)
        l.sort( key = lambda x : x[1] )
        #更新为F(X)型的概率分布函数
        for i in range ( 1 , len(l) , 1 ) :
            l[i][1] = l[i][1] + l[i-1][1]
        #找到对应概率的
        for i in l :
            if i[1] >= k :
                return i[0]


#基础信息素设置为n
n = int ( input() )
BASE_INFORMATION = n
zhengfa_rate = 0.75
#每次的蚂蚁数量
ant_army = 55
#记录答案
ans = 999999999
#创建城市字典
city_list = {}
for i in range ( 1 , n + 1 , 1 ) :
    a_city = City(i)
    l = list(map ( int  , input().split() ) )
    for u in range ( 1 , n + 1 , 1 ) :
        x = l[u-1]
        if u == i :
            continue
        a_city.add_point( u , x , n / ant_army )
    city_list[i] = a_city

#派蚂蚁
#假设从1号村庄开始
for _ in range ( 100 ) :
    #对每一个周期
    #生成ant_army只蚂蚁
    #记录每一只蚂蚁
    ant_list = []
    for z in range ( ant_army ) :
        q = Ant( city_list[1] , n )
        ant_list.append(q)

    #对于每一只蚂蚁
    for i in range ( ant_army ) :
        #一直走，直到到达目的地
        while ( 1 ) :
            #找到下一个去处
            to = ant_list[i].choose( 1 , 1 , 1 )
            #找不到，全找完了，结束
            if to == -1 :
                break
            #访问
            ant_list[i].go_to( city_list[to] )
        #比较，看看是不是路径更短
        if ant_list[i].way < ans :
            ans = ant_list[i].way
        #记录这只蚂蚁对信息素的贡献
        ant_list[i].carry_infor = BASE_INFORMATION / ant_list[i].way

    #全部蚂蚁都走完了，更新信息素
    #所有路径先蒸发
    for i in range ( 1 , n + 1 , 1 ) :
        for u in city_list[i].distance :
            city_list[i].way_infor[u] = city_list[i].way_infor[u] * ( 1 - zhengfa_rate )

    #增加
    for i in range ( ant_army ) :
        #对每只蚂蚁
        ant = ant_list[i]
        for u in range ( n - 1 ) :
            #对每条路径，增加信息素
            #注意，增加是双向的
            city_id1 = ant.went_list[u]
            city_id2 = ant.went_list[u+1]
            city_list[city_id1].add_infor( city_id2 , ant.carry_infor )
            city_list[city_id2].add_infor(city_id1, ant.carry_infor)
#输出答案

print( ans )