Где экономия? Пусть вновь имеются N станций и таблица цен на проезд между ними. Требуется найти все такие пары станций, для которых дешевле проехать от одной до другой с одной пересадкой через какую-то третью станцию, чем напрямую.
Формат ввода На первой строке вводится натуральное число N — количество станций. Далее следует N-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)
Объяснение:
у меня приняли))