Задача 19: Издевательство

Условие задачи:

Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо. Через некоторое время он снова увидел голосующего Бормана, и снова проехал мимо. Вскоре он опять увидел голосующего Бормана.
- Издевается! - подумал Борман.
- Кольцевая! - догадался Штирлиц.

В городе N площадей. Любые две площади соединены между собой ровно одной дорогой с двусторонним движением. В этом городе живет Штирлиц. У Штирлица есть хобби - он любит воскресным утром выйти из дома, сесть в машину, выбрать какой-нибудь кольцевой маршрут, проходящий ровно по трем площадям (то есть сначала он едет с какой-то площади на какую-то другую, потом - на третью, затем возвращается на начальную, и опять едет по этому маршруту). Он воображает, что где-то на этом пути стоит Борман. И так вот ездит Штирлиц все воскресенье, пока голова не закружится, и радуется...

Естественно, что Штирлицу хочется проезжать мимо точки, в которой, как он воображает, стоит Борман, как можно чаще. Для этого, естественно, выбранный Штирлицем маршрут должен быть как можно короче. Напишите программу, которая выберет оптимальный для Штирлица маршрут.

Входные данные:

В первой строке задается число \(N\) \((3 <= N <= 100)\). В последующих строках содержится матрица \(NxN\) расстояний между площадями (число в позиции \(i,j\) обозначает длину дороги, соединяющей \(i\)-ую и \(j\)-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0.

Выходные данные:

Требуется вывести три числа — номера площадей в оптимальном маршруте. Если маршрутов несколько, выведите любой из них.

Решение:

n = int(input())
u = [[int(i) for i in input().split()] for i in range(n)]

s = [[0 for _ in range(n)] for _ in range(n)]

ans = 1000000
ans_i = []
for i in range(n):
    for j in range(n):
        for p in range(n):
            if i != j and j != p and p != i:
                s = u[i][j] + u[j][p] + u[i][p]
                if s < ans:
                    ans_i = [i, j, p]
                    ans = s

print(*[i + 1 for i in ans_i])

У вас включен блокировщик рекламы. Пожалуйста, выключите его чтобы увидеть решения. На этом сайте не так много рекламы, а кушать что-то надо. Вот котик