mst.py

def calcPathDistance(points, order):
    dist = 0
    for i in range(len(order) - 1):
        # cityA = points[order[i % len(order)]]
        # cityB = points[order[(i+1) % len(order)]]
        # # print(cityA, cityB)
        # d = (cityA - cityB).length()
        dist += points[order[i]][order[i + 1]]
    return dist


class ApproxMSTSolver:
    def __init__(self, cities): 
        self.cities = cities
        self.total = len(cities)
        self.bestOrder = []
        self.bestDistance = float('inf')
        self.graph = cities
        self.parent = [None] * self.total

    def printMST(self): 
        print("Edge")
        for i in range(1, self.total): 
            print(i, "-", self.parent[i], "\t") 
   
    def minKey(self, key, mstSet):  
        mini = float('inf') 
        for v in range(self.total): 
            if key[v] < mini and mstSet[v] == False: 
                mini = key[v] 
                min_index = v 
        return min_index

    def primMST(self):  
        key = [float('inf')] * self.total
        key[0] = 0 
        mstSet = [False] * self.total 
        self.parent[0] = -1
        for cout in range(self.total): 
            u = self.minKey(key, mstSet)  
            mstSet[u] = True
            for v in range(self.total):  
                if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]: 
                        key[v] = self.graph[u][v] 
                        self.parent[v] = u
    
    def getListOfIndices(self, l):
        listOfIndices = []
        for i in range(len(l) + 1):
            indices = []
            for j in range(len(l)):
                if i == l[j]:
                    indices.append(j+1)
            listOfIndices.append(indices)
        return listOfIndices

    def preorder(self, l, i, ind):
        if len(l[i]) <= ind:
            return 
        for j in range(len(l[i])):
            self.bestOrder.append(l[i][j])
            self.preorder(l, l[i][j], 0)


    def find(self):
        self.primMST()
        listOfIndices = self.getListOfIndices(self.parent[1:])
        root = 0
        self.bestOrder.append(0)
        self.preorder(listOfIndices, 0, 0)
        print(self.bestOrder)
        self.bestDistance = calcPathDistance(self.cities, self.bestOrder)



cities = [
[
    0.09503960609436035,   33.40936182736597,   37.03155779447229,
     45.559175932713885,   62.70071897667193,    37.2551619153051,
    0.09503960609436035,   50.38963706027438,   76.76306094559949,
      59.29816463780496, 0.09503960609436035,  28.445435076551632,
    0.09503960609436035,    52.8592825581285, 0.16461342648676486,
     10.608736164741906,  11.321287658657855, 0.09503960609436035,
    0.09503960609436035,   43.19484750238829,   21.80988130355493,
    0.09503960609436035,  55.402221387436605,  59.748853864897136,
      66.58540188192704,  45.559175932713885, 0.09503960609436035,
      33.40936182736597, 0.09503960609436035,  13.703511617300398,
     57.153424507131085,   12.64883970598915, 0.09503960609436035,
    0.09503960609436035,   67.80254988031227,   37.03155779447229,
      58.96026145780986,   42.26228658562438,   37.03155779447229,
      33.40936182736597,   37.03155779447229,  45.559175932713885,
     45.559175932713885,   55.60726662958524,   33.40936182736597
  ],
  [
     33.40936182736597,                  0,  34.18692338795673,
      73.8511556478229,  81.47566446354368,  69.79033371146834,
     33.40936182736597,  83.12646631066988, 108.70154687502966,
     55.84804149581943,  33.40936182736597,  27.79205746198909,
     33.40936182736597,  74.82001666820756,  33.51786999795864,
     36.01938379402438, 22.469782963697522,  33.40936182736597,
     33.40936182736597,  75.47778414378277, 35.498787778374975,
     33.40936182736597,  59.83511246492923,  92.91243187122822,
     99.93458643411931,   73.8511556478229,  33.40936182736597,
                     0,  33.40936182736597,  30.31480387890601,
    51.298326205442415, 28.444482444473383,  33.40936182736597,
     33.40936182736597,  85.97460531401438,  34.18692338795673,
     39.17200071881363, 34.420742266843845,  34.18692338795673,
                     0,  34.18692338795673,   73.8511556478229,
      73.8511556478229,  33.36729449475762,                  0
  ],
  [
     37.03155779447229,   34.18692338795673, 0.09503960609436035,
     81.81624023892184,   51.06263205704392,   69.86755696651956,
     37.03155779447229,   81.49722420225542,  108.54188772263252,
    23.648443760135574,   37.03155779447229,   9.065702437488502,
     37.03155779447229,  47.461508011964824,  36.995196711476055,
    29.373081561131396,   34.81642072014749,   37.03155779447229,
     37.03155779447229,   75.89220511602608,  17.893461791307423,
     37.03155779447229,   25.65065972532697,   88.53203302730391,
     93.45080686172777,   81.81624023892184,   37.03155779447229,
     34.18692338795673,   37.03155779447229,   45.94435145864352,
    20.504781248986717,   24.38891105657685,   37.03155779447229,
     37.03155779447229,  104.43512210859835, 0.09503960609436035,
    26.676349415801777,    6.36552550033394, 0.09503960609436035,
     34.18692338795673, 0.09503960609436035,   81.81624023892184,
     81.81624023892184,   67.55243785460603,   34.18692338795673
  ],
  [
    45.559175932713885,   73.8511556478229,  81.81624023892184,
                     0,  89.06093485575074, 18.996037553310565,
    45.559175932713885, 23.017839173151344,  38.27052705731445,
    102.30853577000671, 45.559175932713885,  73.70203494756808,
    45.559175932713885,  77.39976740067027,  45.55382261923511,
     52.55827704719079,   52.9872866133951, 45.559175932713885,
    45.559175932713885,  17.21712699938038,  64.67101269322147,
    45.559175932713885,  95.34713191796658,  33.11158598739115,
     41.40477638697952,                  0, 45.559175932713885,
      73.8511556478229, 45.559175932713885, 43.536439202327536,
     101.0622767972522,  57.89331969031223, 45.559175932713885,
    45.559175932713885,  33.64670518496798,  81.81624023892184,
    104.48596547512383,   87.4508989603486,  81.81624023892184,
      73.8511556478229,  81.81624023892184,                  0,
                     0,  80.17479432495617,   73.8511556478229
  ],
  [
     62.70071897667193,  81.47566446354368, 51.06263205704392,
     89.06093485575074,                  0, 70.52290999177904,
     62.70071897667193,  75.15439762660557, 97.48770693721039,
    46.567079427616406,  62.70071897667193,  54.2080786402376,
     62.70071897667193, 11.662021905399598, 62.55627873489579,
     52.63169479050212,  69.73686121759293, 62.70071897667193,
     62.70071897667193,  74.58665658859832,  46.6867010713474,
     62.70071897667193,  33.03634671651869,  75.7318972953352,
     75.96905173755943,  89.06093485575074, 62.70071897667193,
     81.47566446354368,  62.70071897667193, 76.39304584223588,
     50.53230027090082,  56.57994395012157, 62.70071897667193,
     62.70071897667193, 120.99135372361197, 51.06263205704392,
     72.62518520915494, 55.222100473483195, 51.06263205704392,
     81.47566446354368,  51.06263205704392, 89.06093485575074,
     89.06093485575074,  113.1300708582047, 81.47566446354368
  ],
  [
      37.2551619153051,  69.79033371146834,  69.86755696651956,
    18.996037553310565,  70.52290999177904,                  0,
      37.2551619153051, 13.359404761829216,  39.56833355292129,
     88.17673036957781,   37.2551619153051,  62.78486429017044,
      37.2551619153051, 58.872337502580734,  37.18721385595715,
     40.88625504248535, 47.380174809146055,   37.2551619153051,
      37.2551619153051,  6.067666679828985,  52.01957916953007,
      37.2551619153051,   79.7633730972069, 23.781940490877446,
    31.694675576469947, 18.996037553310565,   37.2551619153051,
     69.79033371146834,   37.2551619153051,  41.18845918203902,
     87.66232974331949, 47.819185125945744,   37.2551619153051,
      37.2551619153051, 52.445245218707996,  69.86755696651956,
     94.68468323857478,  75.96090682543496,  69.86755696651956,
     69.79033371146834,  69.86755696651956, 18.996037553310565,
    18.996037553310565,  83.96457405163027,  69.79033371146834
  ],
  [
    0.09503960609436035,   33.40936182736597,   37.03155779447229,
     45.559175932713885,   62.70071897667193,    37.2551619153051,
    0.09503960609436035,   50.38963706027438,   76.76306094559949,
      59.29816463780496, 0.09503960609436035,  28.445435076551632,
    0.09503960609436035,    52.8592825581285, 0.16461342648676486,
     10.608736164741906,  11.321287658657855, 0.09503960609436035,
    0.09503960609436035,   43.19484750238829,   21.80988130355493,
    0.09503960609436035,  55.402221387436605,  59.748853864897136,
      66.58540188192704,  45.559175932713885, 0.09503960609436035,
      33.40936182736597, 0.09503960609436035,  13.703511617300398,
     57.153424507131085,   12.64883970598915, 0.09503960609436035,
    0.09503960609436035,   67.80254988031227,   37.03155779447229,
      58.96026145780986,   42.26228658562438,   37.03155779447229,
      33.40936182736597,   37.03155779447229,  45.559175932713885,
     45.559175932713885,   55.60726662958524,   33.40936182736597
  ],
  [
     50.38963706027438,  83.12646631066988,  81.49722420225542,
    23.017839173151344,  75.15439762660557, 13.359404761829216,
     50.38963706027438,                  0,  27.05742700707414,
      98.3675992453737,  50.38963706027438,   74.9183416313756,
     50.38963706027438,  63.80322409862106,   50.3138453905299,
    53.141249359594816,  60.69437894186855,  50.38963706027438,
     50.38963706027438,  8.266806953911958,  63.61160653242875,
     50.38963706027438,  88.89074223598936,  11.05895166269409,
     19.42252419766314, 23.017839173151344,  50.38963706027438,
     83.12646631066988,  50.38963706027438,  54.47303447643468,
     98.33361841974757, 60.432486307241575,  50.38963706027438,
     50.38963706027438,  55.35516567350549,  81.49722420225542,
    106.92618830427139,  87.72104158350545,  81.49722420225542,
     83.12646631066988,  81.49722420225542, 23.017839173151344,
    23.017839173151344,  96.69335315811428,  83.12646631066988
  ],
  [
     76.76306094559949, 108.70154687502966, 108.54188772263252,
     38.27052705731445,  97.48770693721039,  39.56833355292129,
     76.76306094559949,  27.05742700707414,                  0,
    124.90749943580272,  76.76306094559949, 101.95668039043025,
     76.76306094559949,  86.82262055472755,  76.70090727960351,
     80.14053823627043,  86.51820281797319,  76.76306094559949,
     76.76306094559949,  33.57347230683992,  90.66145798256379,
     76.76306094559949, 114.85500024389367, 21.930891070290233,
     22.56245052700074,  38.27052705731445,  76.76306094559949,
    108.70154687502966,  76.76306094559949,  79.01730253445879,
      125.097070641332,  87.30798813724519,  76.76306094559949,
     76.76306094559949, 59.195256721558145, 108.54188772263252,
     133.9560912251002, 114.77448104354261, 108.54188772263252,
    108.70154687502966, 108.54188772263252,  38.27052705731445,
     38.27052705731445,  118.3313323878035, 108.70154687502966
  ],
  [
      59.29816463780496,  55.84804149581943, 23.648443760135574,
     102.30853577000671, 46.567079427616406,  88.17673036957781,
      59.29816463780496,   98.3675992453737, 124.90749943580272,
    0.09503960609436035,  59.29816463780496,  32.63638485882054,
      59.29816463780496,  48.63400539908384,  59.23644134115076,
       50.1809120179517,  58.34905512531258,  59.29816463780496,
      59.29816463780496,  93.96456799249735, 37.939020335141336,
      59.29816463780496, 13.591328267876435, 103.68368030739965,
     107.21356420654769, 102.30853577000671,  59.29816463780496,
      55.84804149581943,  59.29816463780496,  69.32401512179308,
      5.362794523138502,  46.94956541072001,  59.29816463780496,
      59.29816463780496, 127.09823162182754, 23.648443760135574,
     29.071868288892762,  21.47306276101388, 23.648443760135574,
      55.84804149581943, 23.648443760135574, 102.30853577000671,
     102.30853577000671,   88.7835258164382,  55.84804149581943
  ],
  [
    0.09503960609436035,   33.40936182736597,   37.03155779447229,
     45.559175932713885,   62.70071897667193,    37.2551619153051,
    0.09503960609436035,   50.38963706027438,   76.76306094559949,
      59.29816463780496, 0.09503960609436035,  28.445435076551632,
    0.09503960609436035,    52.8592825581285, 0.16461342648676486,
     10.608736164741906,  11.321287658657855, 0.09503960609436035,
    0.09503960609436035,   43.19484750238829,   21.80988130355493,
    0.09503960609436035,  55.402221387436605,  59.748853864897136,
      66.58540188192704,  45.559175932713885, 0.09503960609436035,
      33.40936182736597, 0.09503960609436035,  13.703511617300398,
     57.153424507131085,   12.64883970598915, 0.09503960609436035,
    0.09503960609436035,   67.80254988031227,   37.03155779447229,
      58.96026145780986,   42.26228658562438,   37.03155779447229,
      33.40936182736597,   37.03155779447229,  45.559175932713885,
     45.559175932713885,   55.60726662958524,   33.40936182736597
  ],
  [
    28.445435076551632,  27.79205746198909,  9.065702437488502,
     73.70203494756808,   54.2080786402376,  62.78486429017044,
    28.445435076551632,   74.9183416313756, 101.95668039043025,
     32.63638485882054, 28.445435076551632,                  0,
    28.445435076551632, 48.731135187279676, 28.422563094233485,
    21.899773323055676, 25.754856487532255, 28.445435076551632,
    28.445435076551632,  68.84830699164687, 12.367205628640516,
    28.445435076551632, 33.073236711731454,  82.61484152612957,
      88.0670549721844,  73.70203494756808, 28.445435076551632,
     27.79205746198909, 28.445435076551632, 36.884306662587036,
    29.564192551547073, 15.846839055542308, 28.445435076551632,
    28.445435076551632,   95.5068128991786,  9.065702437488502,
     32.01311473327211,  13.81707222579672,  9.065702437488502,
     27.79205746198909,  9.065702437488502,  73.70203494756808,
     73.70203494756808,   60.7824907297347,  27.79205746198909
  ],
  [
    0.09503960609436035,   33.40936182736597,   37.03155779447229,
     45.559175932713885,   62.70071897667193,    37.2551619153051,
    0.09503960609436035,   50.38963706027438,   76.76306094559949,
      59.29816463780496, 0.09503960609436035,  28.445435076551632,
    0.09503960609436035,    52.8592825581285, 0.16461342648676486,
     10.608736164741906,  11.321287658657855, 0.09503960609436035,
    0.09503960609436035,   43.19484750238829,   21.80988130355493,
    0.09503960609436035,  55.402221387436605,  59.748853864897136,
      66.58540188192704,  45.559175932713885, 0.09503960609436035,
      33.40936182736597, 0.09503960609436035,  13.703511617300398,
     57.153424507131085,   12.64883970598915, 0.09503960609436035,
    0.09503960609436035,   67.80254988031227,   37.03155779447229,
      58.96026145780986,   42.26228658562438,   37.03155779447229,
      33.40936182736597,   37.03155779447229,  45.559175932713885,
     45.559175932713885,   55.60726662958524,   33.40936182736597
  ],
  [
     52.8592825581285,  74.82001666820756, 47.461508011964824,
    77.39976740067027, 11.662021905399598, 58.872337502580734,
     52.8592825581285,  63.80322409862106,  86.82262055472755,
    48.63400539908384,   52.8592825581285, 48.731135187279676,
     52.8592825581285,                  0,  52.70955160868273,
    43.29187069281748,  60.85140396172195,   52.8592825581285,
     52.8592825581285,  62.99742425723613,  39.34823339439688,
     52.8592825581285, 35.289397237353384,   64.9447430339777,
    65.78649497321724,  77.39976740067027,   52.8592825581285,
    74.82001666820756,   52.8592825581285,  66.54028188627136,
     51.6505066166909,  48.25214245694925,   52.8592825581285,
     52.8592825581285, 109.41291988216418, 47.461508011964824,
    71.62620048044757,  52.56643963793151, 47.461508011964824,
    74.82001666820756, 47.461508011964824,  77.39976740067027,
    77.39976740067027, 105.27866244299322,  74.82001666820756
  ],
  [
    0.16461342648676486,   33.51786999795864,  36.995196711476055,
      45.55382261923511,   62.55627873489579,   37.18721385595715,
    0.16461342648676486,    50.3138453905299,   76.70090727960351,
      59.23644134115076, 0.16461342648676486,  28.422563094233485,
    0.16461342648676486,   52.70955160868273, 0.09503960609436035,
     10.487137141410683,  11.450990808208214, 0.16461342648676486,
    0.16461342648676486,   43.13112613853313,  21.726062268105856,
    0.16461342648676486,  55.309866338727765,   59.65898839586128,
      66.48596161689372,   45.55382261923511, 0.16461342648676486,
      33.51786999795864, 0.16461342648676486,  13.850371930709805,
      57.10401565291315,  12.615590391346574, 0.16461342648676486,
    0.16461342648676486,    67.8663978961841,  36.995196711476055,
     58.974047563179056,  42.239732531185915,  36.995196711476055,
      33.51786999795864,  36.995196711476055,   45.55382261923511,
      45.55382261923511,   55.75917883696699,   33.51786999795864
  ],
  [
    10.608736164741906,  36.01938379402438, 29.373081561131396,
     52.55827704719079,  52.63169479050212,  40.88625504248535,
    10.608736164741906, 53.141249359594816,  80.14053823627043,
      50.1809120179517, 10.608736164741906, 21.899773323055676,
    10.608736164741906,  43.29187069281748, 10.487137141410683,
                     0, 17.715392773374155, 10.608736164741906,
    10.608736164741906,  46.95062353206261, 12.244996678689937,
    10.608736164741906,  45.23705549797745,   61.2495422265001,
     67.17935582354231,  52.55827704719079, 10.608736164741906,
     36.01938379402438, 10.608736164741906, 23.973540478737682,
     48.58383390311761,  8.017761078568975, 10.608736164741906,
    10.608736164741906,  77.38220210832138, 29.373081561131396,
    53.832701444971114, 35.257003958276016, 29.373081561131396,
     36.01938379402438, 29.373081561131396,  52.55827704719079,
     52.55827704719079,  62.84619263911705,  36.01938379402438
  ],
  [
    11.321287658657855, 22.469782963697522,  34.81642072014749,
      52.9872866133951,  69.73686121759293, 47.380174809146055,
    11.321287658657855,  60.69437894186855,  86.51820281797319,
     58.34905512531258, 11.321287658657855, 25.754856487532255,
    11.321287658657855,  60.85140396172195, 11.450990808208214,
    17.715392773374155,                  0, 11.321287658657855,
    11.321287658657855,  53.13479002939044,  24.39872345927397,
    11.321287658657855,  57.07759402568958,   70.4439048339491,
     77.51247556258768,   52.9872866133951, 11.321287658657855,
    22.469782963697522, 11.321287658657855,  11.36230190159177,
     55.28985752703558, 13.554393886062442, 11.321287658657855,
    11.321287658657855,   70.5743790989115,  34.81642072014749,
     52.62019515299419,  38.80002831178779,  34.81642072014749,
    22.469782963697522,  34.81642072014749,   52.9872866133951,
      52.9872866133951,  45.25831546047496, 22.469782963697522
  ],
  [
    0.09503960609436035,   33.40936182736597,   37.03155779447229,
     45.559175932713885,   62.70071897667193,    37.2551619153051,
    0.09503960609436035,   50.38963706027438,   76.76306094559949,
      59.29816463780496, 0.09503960609436035,  28.445435076551632,
    0.09503960609436035,    52.8592825581285, 0.16461342648676486,
     10.608736164741906,  11.321287658657855, 0.09503960609436035,
    0.09503960609436035,   43.19484750238829,   21.80988130355493,
    0.09503960609436035,  55.402221387436605,  59.748853864897136,
      66.58540188192704,  45.559175932713885, 0.09503960609436035,
      33.40936182736597, 0.09503960609436035,  13.703511617300398,
     57.153424507131085,   12.64883970598915, 0.09503960609436035,
    0.09503960609436035,   67.80254988031227,   37.03155779447229,
      58.96026145780986,   42.26228658562438,   37.03155779447229,
      33.40936182736597,   37.03155779447229,  45.559175932713885,
     45.559175932713885,   55.60726662958524,   33.40936182736597
  ],
  [
    0.09503960609436035,   33.40936182736597,   37.03155779447229,
     45.559175932713885,   62.70071897667193,    37.2551619153051,
    0.09503960609436035,   50.38963706027438,   76.76306094559949,
      59.29816463780496, 0.09503960609436035,  28.445435076551632,
    0.09503960609436035,    52.8592825581285, 0.16461342648676486,
     10.608736164741906,  11.321287658657855, 0.09503960609436035,
    0.09503960609436035,   43.19484750238829,   21.80988130355493,
    0.09503960609436035,  55.402221387436605,  59.748853864897136,
      66.58540188192704,  45.559175932713885, 0.09503960609436035,
      33.40936182736597, 0.09503960609436035,  13.703511617300398,
     57.153424507131085,   12.64883970598915, 0.09503960609436035,
    0.09503960609436035,   67.80254988031227,   37.03155779447229,
      58.96026145780986,   42.26228658562438,   37.03155779447229,
      33.40936182736597,   37.03155779447229,  45.559175932713885,
     45.559175932713885,   55.60726662958524,   33.40936182736597
  ],
  [
     43.19484750238829, 75.47778414378277,  75.89220511602608,
     17.21712699938038, 74.58665658859832,  6.067666679828985,
     43.19484750238829, 8.266806953911958,  33.57347230683992,
     93.96456799249735, 43.19484750238829,  68.84830699164687,
     43.19484750238829, 62.99742425723613,  43.13112613853313,
     46.95062353206261, 53.13479002939044,  43.19484750238829,
     43.19484750238829,                 0,   58.0300659069938,
     43.19484750238829, 85.28659594419798, 19.276412645457867,
     27.56083031403284, 17.21712699938038,  43.19484750238829,
     75.47778414378277, 43.19484750238829, 46.446080115726964,
     93.54726751210616, 53.87798538638765,  43.19484750238829,
     43.19484750238829, 50.74972582022581,  75.89220511602608,
    100.75211353230596, 82.00106216642118,  75.89220511602608,
     75.47778414378277, 75.89220511602608,  17.21712699938038,
     17.21712699938038, 88.43005079466685,  75.47778414378277
  ],
  [
     21.80988130355493, 35.498787778374975, 17.893461791307423,
     64.67101269322147,   46.6867010713474,  52.01957916953007,
     21.80988130355493,  63.61160653242875,  90.66145798256379,
    37.939020335141336,  21.80988130355493, 12.367205628640516,
     21.80988130355493,  39.34823339439688, 21.726062268105856,
    12.244996678689937,  24.39872345927397,  21.80988130355493,
     21.80988130355493,   58.0300659069938,                  0,
     21.80988130355493, 33.669113468689595,  70.81707106504635,
     76.00364302096953,  64.67101269322147,  21.80988130355493,
    35.498787778374975,  21.80988130355493, 33.680244973660805,
     36.39619859466568, 10.886495449839181,  21.80988130355493,
     21.80988130355493,  89.42711826272766, 17.893461791307423,
     43.80336162784113, 24.117786457544092, 17.893461791307423,
    35.498787778374975, 17.893461791307423,  64.67101269322147,
     64.67101269322147,  66.44437663012802, 35.498787778374975
  ],
  [
    0.09503960609436035,   33.40936182736597,   37.03155779447229,
     45.559175932713885,   62.70071897667193,    37.2551619153051,
    0.09503960609436035,   50.38963706027438,   76.76306094559949,
      59.29816463780496, 0.09503960609436035,  28.445435076551632,
    0.09503960609436035,    52.8592825581285, 0.16461342648676486,
     10.608736164741906,  11.321287658657855, 0.09503960609436035,
    0.09503960609436035,   43.19484750238829,   21.80988130355493,
    0.09503960609436035,  55.402221387436605,  59.748853864897136,
      66.58540188192704,  45.559175932713885, 0.09503960609436035,
      33.40936182736597, 0.09503960609436035,  13.703511617300398,
     57.153424507131085,   12.64883970598915, 0.09503960609436035,
    0.09503960609436035,   67.80254988031227,   37.03155779447229,
      58.96026145780986,   42.26228658562438,   37.03155779447229,
      33.40936182736597,   37.03155779447229,  45.559175932713885,
     45.559175932713885,   55.60726662958524,   33.40936182736597
  ],
  [
    55.402221387436605,  59.83511246492923,  25.65065972532697,
     95.34713191796658,  33.03634671651869,   79.7633730972069,
    55.402221387436605,  88.89074223598936, 114.85500024389367,
    13.591328267876435, 55.402221387436605, 33.073236711731454,
    55.402221387436605, 35.289397237353384, 55.309866338727765,
     45.23705549797745,  57.07759402568958, 55.402221387436605,
    55.402221387436605,  85.28659594419798, 33.669113468689595,
    55.402221387436605,                  0,  93.24896568650692,
     96.13259680000277,  95.34713191796658, 55.402221387436605,
     59.83511246492923, 55.402221387436605,  67.17101916416031,
    17.578987580906038, 44.163975407150495, 55.402221387436605,
    55.402221387436605, 122.49926879293149,  25.65065972532697,
     40.65829449688893, 26.882100006517287,  25.65065972532697,
     59.83511246492923,  25.65065972532697,  95.34713191796658,
     95.34713191796658,  93.19727407808531,  59.83511246492923
  ],
  [
    59.748853864897136,  92.91243187122822,  88.53203302730391,
     33.11158598739115,   75.7318972953352, 23.781940490877446,
    59.748853864897136,  11.05895166269409, 21.930891070290233,
    103.68368030739965, 59.748853864897136,  82.61484152612957,
    59.748853864897136,   64.9447430339777,  59.65898839586128,
      61.2495422265001,   70.4439048339491, 59.748853864897136,
    59.748853864897136, 19.276412645457867,  70.81707106504635,
    59.748853864897136,  93.24896568650692,                  0,
      8.41892138123491,  33.11158598739115, 59.748853864897136,
     92.91243187122822, 59.748853864897136,  64.91566876785313,
    104.15595052626156,  68.88948978182701, 59.748853864897136,
    59.748853864897136,    63.750822234706,  88.53203302730391,
    114.55572812117447,  94.85500245380418,  88.53203302730391,
     92.91243187122822,  88.53203302730391,  33.11158598739115,
     33.11158598739115, 107.60439436100633,  92.91243187122822
  ],
  [
     66.58540188192704,  99.93458643411931,  93.45080686172777,
     41.40477638697952,  75.96905173755943, 31.694675576469947,
     66.58540188192704,  19.42252419766314,  22.56245052700074,
    107.21356420654769,  66.58540188192704,   88.0670549721844,
     66.58540188192704,  65.78649497321724,  66.48596161689372,
     67.17935582354231,  77.51247556258768,  66.58540188192704,
     66.58540188192704,  27.56083031403284,  76.00364302096953,
     66.58540188192704,  96.13259680000277,   8.41892138123491,
                     0,  41.40477638697952,  66.58540188192704,
     99.93458643411931,  66.58540188192704,  72.55917595870943,
    108.06584134349333,  75.00112402169783,  66.58540188192704,
     66.58540188192704,  71.26227851324508,  93.45080686172777,
    119.80061844570591,  99.80973278926949,  93.45080686172777,
     99.93458643411931,  93.45080686172777,  41.40477638697952,
     41.40477638697952, 115.65511767433686,  99.93458643411931
  ],
  [
    45.559175932713885,   73.8511556478229,  81.81624023892184,
                     0,  89.06093485575074, 18.996037553310565,
    45.559175932713885, 23.017839173151344,  38.27052705731445,
    102.30853577000671, 45.559175932713885,  73.70203494756808,
    45.559175932713885,  77.39976740067027,  45.55382261923511,
     52.55827704719079,   52.9872866133951, 45.559175932713885,
    45.559175932713885,  17.21712699938038,  64.67101269322147,
    45.559175932713885,  95.34713191796658,  33.11158598739115,
     41.40477638697952,                  0, 45.559175932713885,
      73.8511556478229, 45.559175932713885, 43.536439202327536,
     101.0622767972522,  57.89331969031223, 45.559175932713885,
    45.559175932713885,  33.64670518496798,  81.81624023892184,
    104.48596547512383,   87.4508989603486,  81.81624023892184,
      73.8511556478229,  81.81624023892184,                  0,
                     0,  80.17479432495617,   73.8511556478229
  ],
  [
    0.09503960609436035,   33.40936182736597,   37.03155779447229,
     45.559175932713885,   62.70071897667193,    37.2551619153051,
    0.09503960609436035,   50.38963706027438,   76.76306094559949,
      59.29816463780496, 0.09503960609436035,  28.445435076551632,
    0.09503960609436035,    52.8592825581285, 0.16461342648676486,
     10.608736164741906,  11.321287658657855, 0.09503960609436035,
    0.09503960609436035,   43.19484750238829,   21.80988130355493,
    0.09503960609436035,  55.402221387436605,  59.748853864897136,
      66.58540188192704,  45.559175932713885, 0.09503960609436035,
      33.40936182736597, 0.09503960609436035,  13.703511617300398,
     57.153424507131085,   12.64883970598915, 0.09503960609436035,
    0.09503960609436035,   67.80254988031227,   37.03155779447229,
      58.96026145780986,   42.26228658562438,   37.03155779447229,
      33.40936182736597,   37.03155779447229,  45.559175932713885,
     45.559175932713885,   55.60726662958524,   33.40936182736597
  ],
  [
     33.40936182736597,                  0,  34.18692338795673,
      73.8511556478229,  81.47566446354368,  69.79033371146834,
     33.40936182736597,  83.12646631066988, 108.70154687502966,
     55.84804149581943,  33.40936182736597,  27.79205746198909,
     33.40936182736597,  74.82001666820756,  33.51786999795864,
     36.01938379402438, 22.469782963697522,  33.40936182736597,
     33.40936182736597,  75.47778414378277, 35.498787778374975,
     33.40936182736597,  59.83511246492923,  92.91243187122822,
     99.93458643411931,   73.8511556478229,  33.40936182736597,
                     0,  33.40936182736597,  30.31480387890601,
    51.298326205442415, 28.444482444473383,  33.40936182736597,
     33.40936182736597,  85.97460531401438,  34.18692338795673,
     39.17200071881363, 34.420742266843845,  34.18692338795673,
                     0,  34.18692338795673,   73.8511556478229,
      73.8511556478229,  33.36729449475762,                  0
  ],
  [
    0.09503960609436035,   33.40936182736597,   37.03155779447229,
     45.559175932713885,   62.70071897667193,    37.2551619153051,
    0.09503960609436035,   50.38963706027438,   76.76306094559949,
      59.29816463780496, 0.09503960609436035,  28.445435076551632,
    0.09503960609436035,    52.8592825581285, 0.16461342648676486,
     10.608736164741906,  11.321287658657855, 0.09503960609436035,
    0.09503960609436035,   43.19484750238829,   21.80988130355493,
    0.09503960609436035,  55.402221387436605,  59.748853864897136,
      66.58540188192704,  45.559175932713885, 0.09503960609436035,
      33.40936182736597, 0.09503960609436035,  13.703511617300398,
     57.153424507131085,   12.64883970598915, 0.09503960609436035,
    0.09503960609436035,   67.80254988031227,   37.03155779447229,
      58.96026145780986,   42.26228658562438,   37.03155779447229,
      33.40936182736597,   37.03155779447229,  45.559175932713885,
     45.559175932713885,   55.60726662958524,   33.40936182736597
  ],
  [
    13.703511617300398,  30.31480387890601,  45.94435145864352,
    43.536439202327536,  76.39304584223588,  41.18845918203902,
    13.703511617300398,  54.47303447643468,  79.01730253445879,
     69.32401512179308, 13.703511617300398, 36.884306662587036,
    13.703511617300398,  66.54028188627136, 13.850371930709805,
    23.973540478737682,  11.36230190159177, 13.703511617300398,
    13.703511617300398, 46.446080115726964, 33.680244973660805,
    13.703511617300398,  67.17101916416031,  64.91566876785313,
     72.55917595870943, 43.536439202327536, 13.703511617300398,
     30.31480387890601, 13.703511617300398,                  0,
     66.44791100671333, 23.007437847021368, 13.703511617300398,
    13.703511617300398,  59.23072296755369,  45.94435145864352,
     63.72666038627219, 50.119044135859085,  45.94435145864352,
     30.31480387890601,  45.94435145864352, 43.536439202327536,
    43.536439202327536,  44.50939251319257,  30.31480387890601
  ],
  [
     57.153424507131085, 51.298326205442415, 20.504781248986717,
      101.0622767972522,  50.53230027090082,  87.66232974331949,
     57.153424507131085,  98.33361841974757,   125.097070641332,
      5.362794523138502, 57.153424507131085, 29.564192551547073,
     57.153424507131085,   51.6505066166909,  57.10401565291315,
      48.58383390311761,  55.28985752703558, 57.153424507131085,
     57.153424507131085,  93.54726751210616,  36.39619859466568,
     57.153424507131085, 17.578987580906038, 104.15595052626156,
     108.06584134349333,  101.0622767972522, 57.153424507131085,
     51.298326205442415, 57.153424507131085,  66.44791100671333,
    0.09503960609436035,  44.60193626732891, 57.153424507131085,
     57.153424507131085,  124.8104166869472, 20.504781248986717,
      23.83259067217906, 17.250670292304456, 20.504781248986717,
     51.298326205442415, 20.504781248986717,  101.0622767972522,
      101.0622767972522,   84.0018406744364, 51.298326205442415
  ],
  [
     12.64883970598915, 28.444482444473383,  24.38891105657685,
     57.89331969031223,  56.57994395012157, 47.819185125945744,
     12.64883970598915, 60.432486307241575,  87.30798813724519,
     46.94956541072001,  12.64883970598915, 15.846839055542308,
     12.64883970598915,  48.25214245694925, 12.615590391346574,
     8.017761078568975, 13.554393886062442,  12.64883970598915,
     12.64883970598915,  53.87798538638765, 10.886495449839181,
     12.64883970598915, 44.163975407150495,  68.88948978182701,
     75.00112402169783,  57.89331969031223,  12.64883970598915,
    28.444482444473383,  12.64883970598915, 23.007437847021368,
     44.60193626732891,                  0,  12.64883970598915,
     12.64883970598915,  80.22485625608284,  24.38891105657685,
    47.040476852800836, 29.656164533551763,  24.38891105657685,
    28.444482444473383,  24.38891105657685,  57.89331969031223,
     57.89331969031223,   57.0373843736218, 28.444482444473383
  ],
  [
    0.09503960609436035,   33.40936182736597,   37.03155779447229,
     45.559175932713885,   62.70071897667193,    37.2551619153051,
    0.09503960609436035,   50.38963706027438,   76.76306094559949,
      59.29816463780496, 0.09503960609436035,  28.445435076551632,
    0.09503960609436035,    52.8592825581285, 0.16461342648676486,
     10.608736164741906,  11.321287658657855, 0.09503960609436035,
    0.09503960609436035,   43.19484750238829,   21.80988130355493,
    0.09503960609436035,  55.402221387436605,  59.748853864897136,
      66.58540188192704,  45.559175932713885, 0.09503960609436035,
      33.40936182736597, 0.09503960609436035,  13.703511617300398,
     57.153424507131085,   12.64883970598915, 0.09503960609436035,
    0.09503960609436035,   67.80254988031227,   37.03155779447229,
      58.96026145780986,   42.26228658562438,   37.03155779447229,
      33.40936182736597,   37.03155779447229,  45.559175932713885,
     45.559175932713885,   55.60726662958524,   33.40936182736597
  ],
  [
    0.09503960609436035,   33.40936182736597,   37.03155779447229,
     45.559175932713885,   62.70071897667193,    37.2551619153051,
    0.09503960609436035,   50.38963706027438,   76.76306094559949,
      59.29816463780496, 0.09503960609436035,  28.445435076551632,
    0.09503960609436035,    52.8592825581285, 0.16461342648676486,
     10.608736164741906,  11.321287658657855, 0.09503960609436035,
    0.09503960609436035,   43.19484750238829,   21.80988130355493,
    0.09503960609436035,  55.402221387436605,  59.748853864897136,
      66.58540188192704,  45.559175932713885, 0.09503960609436035,
      33.40936182736597, 0.09503960609436035,  13.703511617300398,
     57.153424507131085,   12.64883970598915, 0.09503960609436035,
    0.09503960609436035,   67.80254988031227,   37.03155779447229,
      58.96026145780986,   42.26228658562438,   37.03155779447229,
      33.40936182736597,   37.03155779447229,  45.559175932713885,
     45.559175932713885,   55.60726662958524,   33.40936182736597
  ],
  [
     67.80254988031227,   85.97460531401438, 104.43512210859835,
     33.64670518496798,  120.99135372361197, 52.445245218707996,
     67.80254988031227,   55.35516567350549, 59.195256721558145,
    127.09823162182754,   67.80254988031227,   95.5068128991786,
     67.80254988031227,  109.41291988216418,   67.8663978961841,
     77.38220210832138,    70.5743790989115,  67.80254988031227,
     67.80254988031227,   50.74972582022581,  89.42711826272766,
     67.80254988031227,  122.49926879293149,    63.750822234706,
     71.26227851324508,   33.64670518496798,  67.80254988031227,
     85.97460531401438,   67.80254988031227,  59.23072296755369,
     124.8104166869472,   80.22485625608284,  67.80254988031227,
     67.80254988031227, 0.09503960609436035, 104.43512210859835,
    122.69705167933266,   109.0870461097551, 104.43512210859835,
     85.97460531401438,  104.43512210859835,  33.64670518496798,
     33.64670518496798,   78.36158167092145,  85.97460531401438
  ],
  [
     37.03155779447229,   34.18692338795673, 0.09503960609436035,
     81.81624023892184,   51.06263205704392,   69.86755696651956,
     37.03155779447229,   81.49722420225542,  108.54188772263252,
    23.648443760135574,   37.03155779447229,   9.065702437488502,
     37.03155779447229,  47.461508011964824,  36.995196711476055,
    29.373081561131396,   34.81642072014749,   37.03155779447229,
     37.03155779447229,   75.89220511602608,  17.893461791307423,
     37.03155779447229,   25.65065972532697,   88.53203302730391,
     93.45080686172777,   81.81624023892184,   37.03155779447229,
     34.18692338795673,   37.03155779447229,   45.94435145864352,
    20.504781248986717,   24.38891105657685,   37.03155779447229,
     37.03155779447229,  104.43512210859835, 0.09503960609436035,
    26.676349415801777,    6.36552550033394, 0.09503960609436035,
     34.18692338795673, 0.09503960609436035,   81.81624023892184,
     81.81624023892184,   67.55243785460603,   34.18692338795673
  ],
  [
     58.96026145780986,  39.17200071881363, 26.676349415801777,
    104.48596547512383,  72.62518520915494,  94.68468323857478,
     58.96026145780986, 106.92618830427139,  133.9560912251002,
    29.071868288892762,  58.96026145780986,  32.01311473327211,
     58.96026145780986,  71.62620048044757, 58.974047563179056,
    53.832701444971114,  52.62019515299419,  58.96026145780986,
     58.96026145780986, 100.75211353230596,  43.80336162784113,
     58.96026145780986,  40.65829449688893, 114.55572812117447,
    119.80061844570591, 104.48596547512383,  58.96026145780986,
     39.17200071881363,  58.96026145780986,  63.72666038627219,
     23.83259067217906, 47.040476852800836,  58.96026145780986,
     58.96026145780986, 122.69705167933266, 26.676349415801777,
                     0, 20.387490830825158, 26.676349415801777,
     39.17200071881363, 26.676349415801777, 104.48596547512383,
    104.48596547512383,  67.94281666675445,  39.17200071881363
  ],
  [
     42.26228658562438,  34.420742266843845,   6.36552550033394,
      87.4508989603486,  55.222100473483195,  75.96090682543496,
     42.26228658562438,   87.72104158350545, 114.77448104354261,
     21.47306276101388,   42.26228658562438,  13.81707222579672,
     42.26228658562438,   52.56643963793151, 42.239732531185915,
    35.257003958276016,   38.80002831178779,  42.26228658562438,
     42.26228658562438,   82.00106216642118, 24.117786457544092,
     42.26228658562438,  26.882100006517287,  94.85500245380418,
     99.80973278926949,    87.4508989603486,  42.26228658562438,
    34.420742266843845,   42.26228658562438, 50.119044135859085,
    17.250670292304456,  29.656164533551763,  42.26228658562438,
     42.26228658562438,   109.0870461097551,   6.36552550033394,
    20.387490830825158, 0.09503960609436035,   6.36552550033394,
    34.420742266843845,    6.36552550033394,   87.4508989603486,
      87.4508989603486,    67.5389985284675, 34.420742266843845
  ],
  [
     37.03155779447229,   34.18692338795673, 0.09503960609436035,
     81.81624023892184,   51.06263205704392,   69.86755696651956,
     37.03155779447229,   81.49722420225542,  108.54188772263252,
    23.648443760135574,   37.03155779447229,   9.065702437488502,
     37.03155779447229,  47.461508011964824,  36.995196711476055,
    29.373081561131396,   34.81642072014749,   37.03155779447229,
     37.03155779447229,   75.89220511602608,  17.893461791307423,
     37.03155779447229,   25.65065972532697,   88.53203302730391,
     93.45080686172777,   81.81624023892184,   37.03155779447229,
     34.18692338795673,   37.03155779447229,   45.94435145864352,
    20.504781248986717,   24.38891105657685,   37.03155779447229,
     37.03155779447229,  104.43512210859835, 0.09503960609436035,
    26.676349415801777,    6.36552550033394, 0.09503960609436035,
     34.18692338795673, 0.09503960609436035,   81.81624023892184,
     81.81624023892184,   67.55243785460603,   34.18692338795673
  ],
  [
     33.40936182736597,                  0,  34.18692338795673,
      73.8511556478229,  81.47566446354368,  69.79033371146834,
     33.40936182736597,  83.12646631066988, 108.70154687502966,
     55.84804149581943,  33.40936182736597,  27.79205746198909,
     33.40936182736597,  74.82001666820756,  33.51786999795864,
     36.01938379402438, 22.469782963697522,  33.40936182736597,
     33.40936182736597,  75.47778414378277, 35.498787778374975,
     33.40936182736597,  59.83511246492923,  92.91243187122822,
     99.93458643411931,   73.8511556478229,  33.40936182736597,
                     0,  33.40936182736597,  30.31480387890601,
    51.298326205442415, 28.444482444473383,  33.40936182736597,
     33.40936182736597,  85.97460531401438,  34.18692338795673,
     39.17200071881363, 34.420742266843845,  34.18692338795673,
                     0,  34.18692338795673,   73.8511556478229,
      73.8511556478229,  33.36729449475762,                  0
  ],
  [
     37.03155779447229,   34.18692338795673, 0.09503960609436035,
     81.81624023892184,   51.06263205704392,   69.86755696651956,
     37.03155779447229,   81.49722420225542,  108.54188772263252,
    23.648443760135574,   37.03155779447229,   9.065702437488502,
     37.03155779447229,  47.461508011964824,  36.995196711476055,
    29.373081561131396,   34.81642072014749,   37.03155779447229,
     37.03155779447229,   75.89220511602608,  17.893461791307423,
     37.03155779447229,   25.65065972532697,   88.53203302730391,
     93.45080686172777,   81.81624023892184,   37.03155779447229,
     34.18692338795673,   37.03155779447229,   45.94435145864352,
    20.504781248986717,   24.38891105657685,   37.03155779447229,
     37.03155779447229,  104.43512210859835, 0.09503960609436035,
    26.676349415801777,    6.36552550033394, 0.09503960609436035,
     34.18692338795673, 0.09503960609436035,   81.81624023892184,
     81.81624023892184,   67.55243785460603,   34.18692338795673
  ],
  [
    45.559175932713885,   73.8511556478229,  81.81624023892184,
                     0,  89.06093485575074, 18.996037553310565,
    45.559175932713885, 23.017839173151344,  38.27052705731445,
    102.30853577000671, 45.559175932713885,  73.70203494756808,
    45.559175932713885,  77.39976740067027,  45.55382261923511,
     52.55827704719079,   52.9872866133951, 45.559175932713885,
    45.559175932713885,  17.21712699938038,  64.67101269322147,
    45.559175932713885,  95.34713191796658,  33.11158598739115,
     41.40477638697952,                  0, 45.559175932713885,
      73.8511556478229, 45.559175932713885, 43.536439202327536,
     101.0622767972522,  57.89331969031223, 45.559175932713885,
    45.559175932713885,  33.64670518496798,  81.81624023892184,
    104.48596547512383,   87.4508989603486,  81.81624023892184,
      73.8511556478229,  81.81624023892184,                  0,
                     0,  80.17479432495617,   73.8511556478229
  ],
  [
    45.559175932713885,   73.8511556478229,  81.81624023892184,
                     0,  89.06093485575074, 18.996037553310565,
    45.559175932713885, 23.017839173151344,  38.27052705731445,
    102.30853577000671, 45.559175932713885,  73.70203494756808,
    45.559175932713885,  77.39976740067027,  45.55382261923511,
     52.55827704719079,   52.9872866133951, 45.559175932713885,
    45.559175932713885,  17.21712699938038,  64.67101269322147,
    45.559175932713885,  95.34713191796658,  33.11158598739115,
     41.40477638697952,                  0, 45.559175932713885,
      73.8511556478229, 45.559175932713885, 43.536439202327536,
     101.0622767972522,  57.89331969031223, 45.559175932713885,
    45.559175932713885,  33.64670518496798,  81.81624023892184,
    104.48596547512383,   87.4508989603486,  81.81624023892184,
      73.8511556478229,  81.81624023892184,                  0,
                     0,  80.17479432495617,   73.8511556478229
  ],
  [
     55.60726662958524,   33.36729449475762,  67.55243785460603,
     80.17479432495617,   113.1300708582047,  83.96457405163027,
     55.60726662958524,   96.69335315811428,  118.3313323878035,
      88.7835258164382,   55.60726662958524,   60.7824907297347,
     55.60726662958524,  105.27866244299322,  55.75917883696699,
     62.84619263911705,   45.25831546047496,  55.60726662958524,
     55.60726662958524,   88.43005079466685,  66.44437663012802,
     55.60726662958524,   93.19727407808531, 107.60439436100633,
    115.65511767433686,   80.17479432495617,  55.60726662958524,
     33.36729449475762,   55.60726662958524,  44.50939251319257,
      84.0018406744364,    57.0373843736218,  55.60726662958524,
     55.60726662958524,   78.36158167092145,  67.55243785460603,
     67.94281666675445,    67.5389985284675,  67.55243785460603,
     33.36729449475762,   67.55243785460603,  80.17479432495617,
     80.17479432495617, 0.09503960609436035,  33.36729449475762
  ],
  [
     33.40936182736597,                  0,  34.18692338795673,
      73.8511556478229,  81.47566446354368,  69.79033371146834,
     33.40936182736597,  83.12646631066988, 108.70154687502966,
     55.84804149581943,  33.40936182736597,  27.79205746198909,
     33.40936182736597,  74.82001666820756,  33.51786999795864,
     36.01938379402438, 22.469782963697522,  33.40936182736597,
     33.40936182736597,  75.47778414378277, 35.498787778374975,
     33.40936182736597,  59.83511246492923,  92.91243187122822,
     99.93458643411931,   73.8511556478229,  33.40936182736597,
                     0,  33.40936182736597,  30.31480387890601,
    51.298326205442415, 28.444482444473383,  33.40936182736597,
     33.40936182736597,  85.97460531401438,  34.18692338795673,
     39.17200071881363, 34.420742266843845,  34.18692338795673,
                     0,  34.18692338795673,   73.8511556478229,
      73.8511556478229,  33.36729449475762,                  0
  ]
]

a = ApproxMSTSolver(cities)
a.find()
print(a.bestDistance)