---

from math import e


# функция вероятности
def probability(delta, T):
    return 100 * e ** (-delta / T)


# изменение температуры
def reduceTemp(prevT):
    return 0.5 * prevT


# длина одного ребра
def edgeLength(i, j, distances):
    if i < j:
        for item in distances:
            if item[0] == i and item[1] == j:
                return item[2]
    else:
        for item in distances:
            if item[0] == j and item[1] == i:
                return item[2]


# длина маршрута
def routeLength(V, distances):
    summ = 0

    for i in range(len(V) - 1):
        summ += edgeLength(V[i], V[i + 1], distances)

    return summ


# одна перестановка в маршруте
def routeOneReplacement(arrV, z):
    arrV = arrV[:]

    first = z[0] - 1
    second = z[1] - 1

    arrV[first], arrV[second] = arrV[second], arrV[first]

    return arrV


# сам алгоритм отжига
def chooseRoute(distances, V, Z, T, P):
    sumLength = routeLength(V, distances)
    arrSum = [sumLength]
    arrV = V[:]

    for i in range(len(Z)):
        newV = routeOneReplacement(arrV, Z[i])
        newS = routeLength(newV, distances)
        arrSum.append(newS)

        delta = newS - sumLength

        if delta > 0:
            p = probability(delta, T)

            if p > P[i]:
                arrV = newV
                sumLength = newS

        else:
            arrV = newV
            sumLength = newS

        T = reduceTemp(T)

    return arrV, arrSum


# данные варианта 4
distances = [
    [1, 2, 17],
    [1, 3, 39],
    [1, 4, 32],
    [1, 5, 28],
    [1, 6, 18],
    [2, 3, 24],
    [2, 4, 28],
    [2, 5, 35],
    [2, 6, 13],
    [3, 4, 25],
    [3, 5, 43],
    [3, 6, 23],
    [4, 5, 20],
    [4, 6, 16],
    [5, 6, 24]
]

V = [1, 5, 2, 6, 3, 4, 1]

Z = [
    [3, 4],
    [4, 5],
    [5, 2],
    [6, 2]
]

P = [78, 79, 25, 82]

T = 100

bestRoute, arrLength = chooseRoute(distances, V, Z, T, P)

print(f"Лучший выбранный маршрут: {bestRoute}")
print(f"Длина лучшего выбранного маршрута: {routeLength(bestRoute, distances)}")
print(f"Длины всех рассмотренных маршрутов: {arrLength}")