ФИПИ ОГЭ информатика, задание 4 (FAEF44)

Задание 4: Задача Задание 4: определить длину кратчайшего пути между A и F через C по таблице дорог между населёнными пунктами, учитывая запрет на повторные посещения.

ОГЭ информатикаЗадание №4Короткий ответКратчайший путь

Задание

№4 · Модели объектов

Впишите правильный ответ.

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.

	A	B	C	D	E	F
A		3				15
B	3		2	3	7
C		2		1	3
D		3	1		1
E		7	3	1		2
F	15				2

Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C. Передвигаться можно только по дорогам, указанным
в таблице. Каждый пункт можно посетить только один раз.

Подсказка AI-репетитора

Подсказки открываются по одной и не показывают готовый ответ.

Показано 0 из 3

Задание 4: кратчайший путь A→C→F по дорожной таблице

Задание 4. Поиск кратчайшего пути через C в дорожной таблице

В задаче даётся неориентированная дорожная таблица между населёнными пунктами A, B, C, D, E, F с указанием расстояний. Нужно найти длину кратчайшего маршрута от A к F, который обязательно проходит через C и не повторяет вершины. Такой подход обучает навыку анализа пути через заданную промежуточную точку: сначала находят путь A→C, затем путь C→F, и суммируют их длины. Важно помнить ограничение на посещение каждого пункта не более одного раза, что влияет на доступные альтернативы и исключает циклы. При решении полезно выписать все допустимые маршруты A→C и C→F, выбрать минимальные по длине и затем сложить их длины, проверяя соответствие условию прохождения через C. В таблице есть взаимные дороги между узлами, например A–B имеет длину 3, B–C — 2, D–C — 1, и т.д.