Демо-вариант

Условие задачи из демо-варианта

Что на самом деле дано в задаче

Перед нами не нарисованный граф, а текстовый файл. Каждая строка файла задаёт одно ориентированное ребро:

L M W

Это означает: из вершины L можно перейти в вершину M, а вес этого ребра равен W.

Значит, перед решением задачи нужно мысленно заменить файл на граф:

файл → список рёбер → ориентированный ациклический граф → поиск кратчайшего пути 1 → 100.

На экзамене рисунка графа нет. Граф нужно восстановить из файла непосредственно в программе.

Разбор условия

Ориентированный

Рёбра односторонние. Порядок чисел в строке задаёт направление, а не «первое и второе».

Взвешенный

У рёбер есть веса, и длина пути — их сумма.

Ациклический

Стрелки не образуют кольца: вернуться в вершину, из которой вышел, нельзя. Отсюда два следствия — путей конечное число, и вопрос про самый длинный путь тоже имеет смысл.

Остальное в условии — про файл: номера вершин до 1000 и не подряд, вес до 10 000, строк не больше 200, разделители — любые пробелы и табуляции. Эти четыре числа определят, как мы будем хранить граф.

Пример из условия

Вершин мало, поэтому можно просто выписать все пути из 1 в 100:

• 1 → 100: 12.0
• 1 → 7 → 100: 5.5 + 2.0 = 7.5
• 1 → 4 → 100: 2.5 + 8.0 = 10.5

Минимум — 7.5. В ответе целая часть: 7.

Целая часть — не округление. 7.5 превращается в 7, а не в 8.

Вершина 12 в файле есть, но стоит после 100 и в путь не попадает. Лишние вершины в файле — норма.

Ручками решить не всегда получится

Каждая развилка умножает число путей. На сорока рёбрах их уже сотни, на двухстах — миллионы, и выписывать бесполезно. Решать нужно программным путём.

Где какая строка

Слева файл целиком, справа граф. Шагай стрелками или нажми «показать всё» — строка за строкой граф нарисуется сам.

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

Стрелками — по одному шагу, кнопка «показать всё» прогоняет целиком. Строки файла идут вразнобой: сначала появляется стрелка из 100, а сама вершина 1 — только на третьей строке. Это нормально.

Ловушки

• Пошли по ребру в обратную сторону. Направление задано порядком чисел.
• Сложили количество рёбер вместо весов.
• Округлили 7.5 до 8. Нужна целая часть.
• Искали путь до вершины с самым большим номером. Финиш всегда назван в условии.
• Решили, что вершины идут подряд. Номера произвольные, до 1000.

Проверь себя