Где экономия? Пусть вновь имеются N станций и таблица - вопрос №16149395 от kkazyna 08.02.2021 01:26

Question

Информатика: Где экономия? Пусть вновь имеются N станций и таблица цен на проезд между ними. Требуется найти все такие пары станций, для которых дешевле проехать от одной до другой с одной пересадкой через какую-то третью станцию, чем напрямую. Формат ввода На первой строке вводится натуральное число N — количество станций. Далее следует N-1 строка, составляющая половину таблицы цен, как в предыдущих задачах на эту тему. Формат вывода Выводится список пар номеров станций, удовлетворяющих условию (каждая пара

kkazyna · Answer

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)

Объяснение:

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