Problem:
Bitonic Traveling Salesman Problem (Bitonic TSP) For given $N$ points in the 2D Euclidean plane, find the distance of the shortest tour that meets the following criteria:  Visit the points according to the following steps:  It starts from the leftmost point (starting point), goes strictly from left to right, and then visits the rightmost point (turn-around point).  Then it starts from the turn-around point, goes strictly from right to left, and then back to the starting point.    Through the processes 1. 2., the tour must visit each point at least once.  Input The input data is given in the following format: $N$ $x_1$ $y_1$ $x_2$ $y_2$ ... $x_N$ $y_N$  Constraints  $2 \leq N \leq 1000$  $-1000 \leq x_i, y_i \leq 1000$  $x_i$ differ from each other  The given points are already sorted by x-coordinates  Output Print the distance of the shortest tour in a line. The output should not have an error greater than 0.0001. Sample Input 1 3
0 0
1 1
2 0 Sample Output 1 4.82842712 Sample Input 2 4
0 1
1 2
2 0
3 1 Sample Output 2 7.30056308 Sample Input 3 5
0 0
1 2
2 1
3 2
4 0 Sample Output 3 10.94427191

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

def calc(p1, p2, v):
    dists_v = dists[v]
    if v == n - 1:
        return dists_v[p1] + dists_v[p2]
    if visited[p1][p2]:
        return dp[p1][p2]
    dp[p1][p2] = min(dists_v[p1] + calc(p2, v, v + 1), dists_v[p2] + calc(p1, v, v + 1))
    visited[p1][p2] = True
    return dp[p1][p2]


n = int(input())
points = [complex(*map(int, input().split())) for _ in range(n)]
dists = [[abs(p1 - p2) for p2 in points] for p1 in points]
visited = [[False] * n for _ in range(n)]
dp = [[0] * n for _ in range(n)]

print(calc(0, 0, 0))

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))



eps = 10 ** (-9)


def main():
    n = ni()
    e = []
    for _ in range(n):
        xi, yi = ns()
        e.append([xi, yi])

    dp = [[INF for _ in range(n)] for _ in range(n)]

    dist = lambda p1, p2: math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

    dp[0][0] = 0

    for i in range(n - 1):
        for j in range(n):
            if dp[i][j] != INF:
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + dist(e[i], e[i + 1]))
                dp[i + 1][i] = min(dp[i + 1][i], dp[i][j] + dist(e[j], e[i + 1]))

    for i in range(n):
        dp[n - 1][n - 1] = min(dp[n - 1][n - 1], dp[n - 1][i] + dist(e[n - 1], e[i]))

    print(dp[n - 1][n - 1])


if __name__ == '__main__':
    main()

Solution (Python):


import sys
from math import sqrt

sys.setrecursionlimit(1000000)

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    P = [list(iim()) for i in range(N)]

    def dist(i, j):
        x = P[i][0] - P[j][0]
        y = P[i][1] - P[j][1]
        return sqrt(x*x + y*y)

    def tsp(i, j, k):
        if i == 0 and j == 0:
            return dist(0, 1) + tsp(0, 1, 0)
        else:
            if dp[i][j]: return dp[i][j]
            if k == N: return dist(i, j)
            d1 = dist(i, k) + tsp(k, j, k + 1)
            d2 = dist(j, k) + tsp(i, k, k + 1)
            d = d1 if d1 < d2 else d2
            dp[i][j] = d
            return d

    dp = [[0]*N for i in range(N)]
    print(tsp(0,0,0))


if __name__ == "__main__":
    resolve()

Solution (Python):
import math
from typing import List, Tuple


def dist(p1: Tuple[int, int], p2: Tuple[int, int]) -> float:
    return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)


if __name__ == "__main__":
    N = int(input())
    points: List[Tuple[int, int]] = [(0, 0)] * N
    for idx in range(N):
        x, y = map(lambda x: int(x), input().split())
        points[idx] = (x, y)

    table1 = [float('inf')] * N
    table2 = [float('inf')] * N
    table1[0] = table2[0] = dist(points[0], points[1])

    for i in range(2, N):
        d1 = d2 = float('inf')
        for j in range(i - 1):
            d = dist(points[i], points[j])
            d1 = min(d1, table2[j] + d)
            d2 = min(d2, table1[j] + d)
        table1[i - 1] = d1
        table2[i - 1] = d2
        d = dist(points[i - 1], points[i])
        for j in range(i - 1):
            table1[j] += d
            table2[j] += d

    ans = min(min(d1, d2) + dist(points[i], points[N - 1])
              for i, (d1, d2) in enumerate(zip(table1, table2)))
    print(ans)

Solution (Python):
import math

pts = []
line = input()
N = int(line)
for _ in range(0, N):
    line = input()
    x, y = list(map(int, line.split()))
    pts += [[x, y]]

def dist(i, j):
    x1, y1 = pts[i]
    x2, y2 = pts[j]
    return math.sqrt((x1 - x2)**2 + (y1 - y2)**2)
    
def btsp():
    dp = [ [0] * N for _ in range(0, N)]
    for i in range(1, N):
        dp[0][i] = dp[0][i - 1] + dist(i - 1, i)
    for i in range(1, N):
        for j in range(i, N):
            if i == j - 1 or i == j:
                m = 10 ** 10
                for k in range(0, i):
                    m = min(m, dp[k][i] + dist(j, k))
                dp[i][j] = m
            else:
                dp[i][j] = dp[i][j - 1] + dist(j - 1, j)
    return dp[N - 1][N - 1]

print(btsp())

Solution (Python):
import sys
from math import sqrt
readline = sys.stdin.readline
write = sys.stdout.write

N = int(readline())
PS = [list(map(int, readline().split())) for i in range(N)]
PS.sort()

def dist(P, Q):
    return sqrt((P[0] - Q[0])**2 + (P[1] - Q[1])**2)


INF = 10**18
S = [INF]*N; T = [INF]*N
S[0] = T[0] = dist(PS[0], PS[1])
for k in range(2, N):
    s = t = INF
    for i in range(k-1):
        d = dist(PS[i], PS[k])
        s = min(s, T[i] + d)
        t = min(t, S[i] + d)
    S[k-1] = s; T[k-1] = t
    d = dist(PS[k-1], PS[k])
    for i in range(k-1):
        S[i] += d; T[i] += d
print(min(min(s, t) + dist(PS[i], PS[N-1]) for i, (s, t) in enumerate(zip(S, T))))