DjangoBB LoFi version

Aress

Янв. 6, 2019 16:39:54

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

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

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

Пример
Ввод:
4
10
10 10
1 1 1
Вывод:
0 1
0 2
1 2

Помогите решить. Вот кусок кода для ввода значений в матрицу:

 n = int(input())
matrix = [[0 for _ in range(n)] for _ in range(n)]
for i in range(1, n):
    matrix[i] = [int(i) for i in input().split()]
    matrix[i] += [0 for _ in range(n - len(matrix[i]))]

ZerG

Янв. 7, 2019 15:36:21

И в чем загвоздка то?

Borol

Янв. 8, 2019 11:35:15

Не получается разделить массив на массив из 2-х значений, функция просто ничего не делит, подскажите как правильно обратиться к нужному мне элементу матрицы, i-й получается массив, а как правильно обратиться к значению в массиве массивов?

 import operator
n = int(input())
array = [[0 for _ in range(n)] for _ in range(n)]
for i in range (1, n):
    array[i] = [int(i) for i in input().split()]
    array[i] += [0 for _ in range(n - len(array[i]))]
a = sorted(array, key=operator.itemgetter(0, 1))
def split(arr, count):
    return [arr[n::count] for n in range(count)]
print(split(a, 2))

uf4JaiD5

Янв. 15, 2019 17:57:23

Тут алгоритм интереснее, а ввод-вывод потом дописать можно.

Допустим, матрица уже есть:

 #
matrix = [[0, 1, 2, 3],
          [1, 0, 3, 1],
          [2, 3, 0, 1],
          [3, 1, 1, 0]]

Cтоимость билета из a в b:

 matrix[a][b]

Стоимость перемещения “из А в Б” в данном случае равна стоимости перемещения “из Б в А”.
Станции обозначим 0,1,2,3. Для наглядности предположим, что они расположены на прямой в этом порядке.

“Аномалии”:
1. Дешёвый билет 1->3. Стоит 1 вместо 2.
В результате билет 0->3 стоит 3, а поездка 0->1->3 стоит 1+1=2.

2. Дорогой билет 1->2, 3 вместо 1.
В результате билет 1->2 стоит 3, а поездка 1->3->2 стоит 1+1=2.

Теперь нужен код, который это обнаружит и покажет.