13
Шешімі: Самый длинный путь в графе
ЕГЭ · Информатика · Тапсырма 13 · Графы и пути
КүрделіФИПИ2B21CFҚысқа жауап≈ 3 минутТалдау 3 қадамЖауап сверен с ключом
Условие
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого протяжённого пути из города А в город Л? Длиной пути считать количество дорог, составляющих этот путь.
Дальше ответЕгер әлі шешіп жатсаңыз – кеңестерден бастаңыз: олар жауапқа жетелейді, бірақ оны ашпайды.
К подсказкамШешім по шагам
3 қадам1
Схему дорог рассматриваем как ориентированный граф: города являются вершинами, а дороги — направленными рёбрами.
2
Для каждого города вычисляем длину самого длинного пути из города А. При прохождении очередной дороги длина пути увеличивается на 1.
Сравнив длины всех путей, ведущих из А в Л, получаем максимальное значение 5.
Жауап
5
5
так ответ выглядит в бланкеГде здесь ошибаются
Считать не дороги, а города маршрута.
Игнорировать направление стрелок.
Выбирать самый короткий путь вместо самого длинного.