Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Prorva
Всем горнолыжным курортам Вася предпочитает Красный Борщ: там невысоко и некруто, зато вкусно. Подъёмник доставляет лыжника на вершину (пункт 0), откуда он, предварительно покушав в ресторане, начинает спуск. Трасса представляет собой совокупность расположенных на склоне кафе, соединённых лыжнями, ехать по которым можно только в одном направлении – вниз (в этом месте особо умные участники сказали «Ага, ориентированный граф!» - и они таки правы).
Цель Васи – выбрать такой маршрут спуска от пункта 0 до пункта N, на котором он сможет покушать наибольшее количество раз. А ваша цель – написать программу, определяющую, сколько раз Вася покушает на оптимальном маршруте.
Входные данные: ов первой строке – два натуральных числа через пробел, N и M, количество кафе (ресторан в пункте 0 в их число не входит) и количество лыжней между кафе. Далее M строк, описывающих лыжни, в каждой пара разделённых пробелом чисел («Ага, список рёбер!» - сказали особо умные участники, и эти зануды опять правы). Гарантируется, что N и M не превышают 100 и что данные корректны (нет циклов и тупиков).
Выходные данные: одно натуральное число, количество перекусов Васи.
Так уж и быть, приведём пример.
При вот таких входных данных –
4 7
0 1
2 4
0 2
1 4
2 1
0 3
3 4
– Вася при верном выборе пути покушает 4 раза: в пунктах 0, 2, 1 и 4.
Для отправки решений необходимо выполнить вход.
|