Question

Где экономия?

Пусть вновь имеются N станций и таблица цен на проезд между ними. Требуется найти все такие пары станций, для которых дешевле проехать от одной до другой с одной пересадкой через какую-то третью станцию, чем напрямую.

Формат ввода
На первой строке вводится натуральное число N — количество станций.
Далее следует N-1 строка, составляющая половину таблицы цен, как в предыдущих задачах на эту тему.

Формат вывода
Выводится список пар номеров станций, удовлетворяющих условию (каждая пара — через пробел). Пары должны быть отсортированы по возрастанию по первому номеру, затем — по второму, и пары не должны повторяться, в том числе с изменённым порядком номеров в паре.

Answer 1

Ответ:

n = int(input())

s = [[]] + [list(map(int, input().split())) for _ in range(n - 1)]

for a in range(0, n - 1):

   for a1 in range(a + 1, n):

       g = s[max(a, a1)][min(a, a1)]

       b = -1

       for i in range(n):

           if i != a and i != a1:

               l_new = s[max(i, a)][min(i, a)] + s[max(i, a1)][min(i, a1)]

               g, b = (l_new, i) if (g > l_new) else (g, b)

       if b != -1:

           print(a, a1)

Объяснение:

у меня приняли))