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 that you have read and understand our privacy policy and code of conduct.

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