Информатика. ЕГЭ
Задание 23. Информатика. ЕГЭ 2027. Демо
- Просмотры: 824
- Изменено: 29 августа 2026
В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа \((L,~M)\) и одно положительное вещественное число \((W).\) \(L\) и \(M\) – номера вершин графа, \(W\) – вес ребра, ведущего из вершины \(L\) в вершину \(M.\) Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером \(1\) в вершину с номером \(100.\) Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. \(L \leqslant 1000,\) \(M \leqslant 1000;\) \(W \leqslant 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\)
Решение:
Python
from collections import defaultdict
def dfs(graph, L, mp):
for M, W in graph[L]:
new_weight = mp[L] + W
if new_weight < mp[M]:
mp[M] = new_weight
if graph[M]:
dfs(graph, M, mp)
min_path = [float('inf')] * 1001
min_path[1] = 0
graph = defaultdict(list)
for line in open('demo_23.txt'):
L, M, W =line.strip().split()
graph[int(L)].append((int(M), float(W)))
dfs(graph, 1, min_path)
print(int(min_path[100]))
Ответ: \(10971\)
Новый тренажёр-эмулятор
Станции КЕГЭ
Эффективно готовьтесь к ЕГЭ по информатике с новым тренажёром, эмулирующем работу станции КЕГЭ, которая используется на реальном экзамене
Новое видео
Поддержать автора сайта!
Расписание пробников Статграда в 2026/27 учебном году
Информатика ОГЭ 9 класс
- 13 октября 2026 года
- 3 декабря 2026 года
- 21 января 2027 года
- 19 февраля 2027 года
- 23 марта 2027 года
- 27 апреля 2027 года
Математика ОГЭ 9 класс
- 23 сентября 2026 года
- 1 декабря 2026 года
- 22 января 2027 года
- 3 марта 2027 года
- 14 апреля 2027 года
Физика ОГЭ 9 класс
- 19 октября 2026 года
- 10 декабря 2026 года
- 29 января 2027 года
- 17 марта 2027 года
- 22 апреля 2027 года
Математика ЕГЭ 10 класс
- 3 февраля 2027 года
- 11 мая 2027 года
Информатика ЕГЭ 11 класс
- 22 октября 2026 года
- 15 декабря 2026 года
- 26 января 2027 года
- 2 марта 2027 года
- 13 апреля 2027 года
Математика ЕГЭ 11 класс
- 30 сентября 2026 года
- 17 декабря 2026 года
- 9 февраля 2027 года
- 16 марта 2027 года
- 21 апреля 2027 года
Физика ЕГЭ 11 класс
- 14 октября 2026 года
- 16 декабря 2026 года
- 4 февраля 2027 года
- 12 марта 2027 года
- 9 апреля 2027 года