求最短路径的算法

02.py

import math
import copy

n = [int(x) for x in input().split(' ')]

#---TEST CASE-----------------------------
# str = '200 0 200 10 200 50 200 30 200 25'
# str = '1 2 2 2 3 1'
# n = [int(x) for x in str.split(' ')]
#---TEST CASE-----------------------------

formN = [(x,y) for x,y in zip(n[::2],n[1::2])]

def countDis(point1, point2):
  return math.sqrt((point2[1] - point1[1]) ** 2 + (point2[0] - point1[0]) ** 2)

# print([countDis(x, (0,0)) for x in formN])

def solver(spoint, mpoint, epoint):
  if len(mpoint) == 1:
    return countDis(spoint, mpoint[0]) + countDis(mpoint[0], epoint)
  else:
    distanList = []
    chooseCan = []
    for i in mpoint:
      temp = copy.deepcopy(mpoint)
      temp.remove(i)
      distanList.append(solver(spoint, temp, i) + countDis(i, epoint))
      chooseCan.append(i)
    return min(distanList)
# print(formN)
print(int(solver((0,0),formN, (0,0))))