Задание №23 ЕГЭ Информатика с ответом и решением
Ответ: 10971
Условие
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. L ≤ 1000, M ≤ 1000; W ≤ 10 000. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.
Типовой пример организации данных во входном файле для графа на рисунке
100 12 1.0
6 7 7.0
6 1 1.0
1 7 5.5
7 100 2.0
4 100 8.0
1 100 12.0
1 4 2.5
Для приведённого примера верным ответом будет 7.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Подсказки — как подойти к решению
- Это поиск кратчайшего пути из вершины 1 в вершину 100 во взвешенном ориентированном графе. Подойдёт алгоритм Дейкстры, а поскольку граф ациклический — и динамика по топологическому порядку вершин.
- Данные лежат в текстовом файле: в каждой строке два номера вершин и вес ребра из L в M, поэтому строк столько же, сколько рёбер. Номера вершин идут не подряд и могут быть больше 100, так что расстояния храни в массиве на 1001 элемент (или в словаре) и читай файл программой.
- Веса дробные, поэтому сумму весов веди как вещественное число, а в ответ запиши целую часть без округления вверх. Проверь, что рёбра направленные (именно из L в M), что путь начинается в вершине 1 и заканчивается в 100, и что в сумму попали веса всех рёбер маршрута.
Решение
Ответ: 10971.
Ответ: 10971
Типичные ошибки
- Похоже, длина пути округлена до ближайшего целого. В задании нужна целая часть длины, то есть дробная часть отбрасывается, поэтому округление вверх даёт лишнюю единицу.
- В ответ попало число рёбер в найденном пути, а не сумма их весов: маленькое число — признак того, что считались шаги. Складывай именно веса W всех рёбер маршрута.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №23 по информатике