0

Она меня вообще в угол загнала. Ничего не понял, понимаю , что нагло, но никогда в таком тупике не был. Как считать? Что за N - 1 в условии? Очень запутанно. Прошу не решение, а помощь в объяснении.

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

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

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

3
  • Если N это например 22, то N-1 будет 21
    – andreymal
    6 янв 2020 в 21:40
  • Скажем, станций 3. Даём для станции 1 цены на поездку на станции 2 и 3. Даём для станции 2 цену на поездку на станцию 3. Всё. Двух строк достаточно. Для станции 3 цены не нужны - они все уже известны.
    – Akina
    6 янв 2020 в 21:46
  • @Akina Хорошо, но как можно считать меньшую цену, ведь то что я получаю это или матрица или словарь с ценами.
    – Xle6yWek
    6 янв 2020 в 21:53

2 ответа 2

1

Собственно если у нас 3 станции, то матрица расстояний выглядит например так

0 1 4
1 0 3
4 3 0

Соответственно на вход подаются строки

1
4 3

Для решения задачи можно использовать основную идею алгоритма Дейкстры.

1
  • Я же написал: основную идею.
    – becouse
    7 янв 2020 в 9:25
0

Вот так в (случайной) матрице цен выглядит путь от станции B до станции E (или обратно) через станцию D. Стоимость такой поездки равна 35+3=38.

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

Остальное, по-моему, совершенно очевидно.

Например, в этой матрице пути от станции B до станции E через станции A..F имеют стоимости 75, 35, 100, 38, 35, 72. Минимальное значение - 35, оно соответствует путям через станции B и E - то есть прямому пути, без промежуточной станции. Если же промежуточная станция обязательна, то минимальная стоимость - 38, через станцию D.

Ваш ответ

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

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