2011-gre-cs-practice-book.pdf/Q61

Ссылки сюда (1) →

Вопрос: Q61-08c765

Какие из следующих задач известны как решаемые за время ?

• I. Найти кратчайший путь от заданной начальной вершины до заданной конечной вершины в направленном графе с n вершинами и неотрицательными целочисленными весами на рёбрах.
• II. Найти самый длинный простой путь от заданной начальной вершины до заданной конечной вершины в направленном графе с n вершинами и неотрицательными целочисленными весами на рёбрах.
• III. Найти самый длинный путь от заданной начальной вершины до заданной конечной вершины в ациклическом направленном графе (DAG) с n вершинами и неотрицательными целочисленными весами на рёбрах.

Ответы

• Только I
• I и II
• Правильный ответ: I и III
• II и III
• I, II и III

Объяснение

Исходники — вопрос 61 на 43 странице книги «2011-gre-cs-practice-book.pdf»

Задача зарезервирована: Nikitashapovalov 20:44, 8 января 2025 (UTC)

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.