3

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

Формат ввода

На первой строке вводится натуральное число N — количество станций. Далее следует N − 1 строка, составляющая половину таблицы цен. После этого следуют номера станций A и B — желаемые пункты отправления и прибытия (на одной строке, через пробел.).

Формат вывода

Выводится одно число — номер станции, пересадкой через которую дешевле всего проехать из A в B. Если таких несколько, выводится наименьший номер. Если дешевле всего не делать пересадок, а ехать напрямую, выводится A (в том числе в том случае, когда существуют маршруты с пересадками за ту же цену).

Пример

Ввод

3
10
1 2
0 1

Вывод

2

есть ли способ сократить код, чтобы выглядел поэлегантнее и краще , чем сейчас?

n = int(input())
s = [[]]
 
for i in range(n - 1):
    s.append([int(j) for j in input().split()])
 
station = input().split()
a, a1 = int(station[0]), int(station[1])
 
l = s[max(a, a1)][min(a, a1)]
b = -1
 
for i in range(n):
    if i != a and i != a1:
        if (l > s[max(a, i)][min(a, i)] + s[max(i, a1)][min(i, a1)]):
            l = s[max(i, a1)][min(i, a1)] + s[max(i, a1)][min(i, a1)]
            b = i
 
if b != -1:
    print(b)
else:
    print(a)

UPDATE

введите сюда описание изображения

5
10
1 1
1 1 1
100 1 1 1
4 0

Ожидаемый результат

2

Вывод

3
4
  • 1
    а есть еще тесткейсы к этой задаче? или ссылка на источник?
    – Jack_oS
    5 янв 2021 в 20:21
  • @Jack_oS да, есть , но в виде таблицы, сейчас добавлю в вопрос , нет, к сожалению доступ к источнику только по специальному логину и паролю
    – Андр
    5 янв 2021 в 20:23
  • А оптимизация и сокращение кода - не разные вещи ?) 5 янв 2021 в 20:39
  • @OPTIMUSPRIME ну по логике в оптимизации написано Оптимизация — улучшение дизайна или реализации
    – Андр
    5 янв 2021 в 20:40

2 ответа 2

2

чуть-чуть поджал ваш код:

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

a, a1 = map(int, input().split())

l = s[max(a, a1)][min(a, a1)]
b = -1

for i in range(n):
    if i != a and i != a1:
        if (l > s[max(i, a)][min(i, a)] + s[max(i, a1)][min(i, a1)]):
            l = s[max(i, a1)][min(i, a1)] + s[max(i, a1)][min(i, a1)]
            b = i

print((a, b)[b != -1])

и сразу вопрос - а у вас случаем вот тут не ошибка:

        if (l > s[max(i, a)][min(i, a)] + s[max(i, a1)][min(i, a1)]):
            l = s[max(i, a1)][min(i, a1)] + s[max(i, a1)][min(i, a1)]

и надо

        if (l > s[max(i, a)][min(i, a)] + s[max(i, a1)][min(i, a1)]):
            l = s[max(i, a)][min(i, a)] + s[max(i, a1)][min(i, a1)]

?

если так, то тогда можно еще чуть поджать:

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

a, a1 = map(int, input().split())

l = 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)]
        l, b = (l_new, i) if (l > l_new) else (l, b)

print((a, b)[b != -1])
0
2

Определяем функцию вычисления стоимости, которая кроме прочего считает стоимость проезда от станции до самой себя равной нулю. Это полезное обобщение, которое позволит рассматривать поездку без пересадки a -> b как частный случай поездки с пересадкой a -> a -> b или a -> b -> b.

Находим первую из оптимальных промежуточных станций, отдавая предпочтение станции a

def cost(i, j):
    return 0 if i == j else table[max(i, j) - 1][min(i, j)]

n = int(input())
table = [[int(x) for x in input().split()] for _ in range(n - 1)]
a, b = map(int, input().split())

print(min(a, *range(n), key=lambda x: cost(a, x) + cost(x, b)))

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.