Список рёбер

Чтение файла

Чтение файла в этом задании всегда одно и то же. Выучи эти четыре строки - дальше начинается собственно задача.

Дальше работаем с файлом graph.txt (прикреплен в конце тетради): 40 рёбер, 20 вершин, номера до 1000.

Как разобрать строку

split() без аргументов

В условии сказано: числа разделены произвольным количеством пробелов и табуляций. Метод split() без аргументов режет строку по любым пробельным символам и сам выбрасывает пустые куски.

split() - всегда без аргументов. Запись split(" ") на двойном пробеле вернёт лишний пустой элемент, и распаковка в три переменные упадёт.

Два целых и одно вещественное

Номера вершин - int, вес - float. Запись int(w) обрежет 5.5 до 5, и ответ уедет.

Где хранить рёбра

Хватит списка троек «откуда, куда, вес». Все алгоритмы дальше работают прямо по этому списку.

edges = []   # список рёбер

for line in f:
    a, b, w = line.split()
    edges.append((int(a), int(b), float(w)))

Где хранить расстояния

Здесь важна строчка условия: номера вершин не превосходят 1000. Значит, можно завести список из 1001 ячейки и обращаться к нему прямо по номеру вершины - никаких словарей и перенумерации.

graph = [[] for _ in range(1001)]

for a, b, w in edges:
    graph[a].append((b, w))

Пример

Первое, что стоит сделать с незнакомым файлом, - посмотреть на его размер и структуру. Откройте прикреплённый внизу тетрадь файл и изучите его структуру.

Что делает split

Возьмём одну строку файла - с табуляцией и лишними пробелами, как обещано в условии, - и посмотрим, во что она превращается.

Результат работы программы

['1', '100', '12.0']
['', '', '1\t100', '', '', '', '12.0\n']
1 100 12.0
1100
101

Сразу видно две вещи. Вызов split с пробелом в скобках выдал пустые куски и не отделил номер от табуляции. А сложение строк дало 1100 вместо 101 — поэтому номера обязательно превращаем в int, а вес в float.

Пример

Результат работы программы

40
20
917
98 18.6
66 19.4
810 30.6
264 16.8
123 43.6
785 35.6

Двадцать вершин, но номера доходят до 917 - вот почему нужен будет список на 1001 ячейку, а не на двадцать одну. Шесть рёбер выходят из вершины 1, и ни одно не ведёт сразу в 100.

Ловушки

• int(w) вместо float(w). Веса вещественные.
• split(" ") с пробелом в скобках. На табуляции сломается.
• Список на 101 элемент. Номера вершин доходят до 1000.
• Посчитали строки файла и решили, что это число вершин. Это число рёбер.
• Забыли, что в файле бывают вершины, до которых из единицы не добраться.

Проверь себя