Когда получал задачу, мне сказали, что она легкая. Не тут то было, видимо ее с чем-то перепутали, потому что все говорят что она очень сложная. В результате я долго парился с этой задачей, одногруппники помочь не могут, до сдачи осталось мало времени.  
Заранее спасибо.

Вот условие:

Служебный автобус совершает один рейс по установленному маршруту и в случае наличия свободных мест подбирает рабочих, которые ожидают на остановках, и отвозит их на завод. Автобус также может ждать на остановке рабочих, которые еще не пришли. Известно время прихода каждого рабочего на свою остановку и время проезда автобуса от каждой остановки до следующей. Автобус приходит на первую остановку в нулевой момент времени. Продолжительность посадки рабочих в автобус считается нулевой.
Задание: Написать программу BUS, которая определит минимальное время, за которое автобус привезет максимально возможное количество рабочих.
Входные данные: Входной текстовый файл BUS.DAT в первой строке содержит количество остановок N и количество мест в автобусе M. Каждая i-я строчка из последующих N строчек содержит целое число - время движения от остановки _ к остановке i+1 (N+1-я остановка - завод), количество рабочих K, которые придут на i-ю остановку, и время прихода каждого рабочего на эту остановку в порядке прихода (1 <= M <= 2000, 1 <= N,K <= 200000).
Пример входных данных.
3 5
1 2 0 1
1 1 2
1 4 0 2 3 4
Выходные данные: Единственная строка выходного текстового файла BUS.SOL должен содержать минимальное время, необходимое для перевозки максимального количества рабочих.
Пример выходных данных.
4

 Поскольку все в целых числах и маршрут один , остается тупо перебирать время ожидания на каждой остановке (ну если в лоб решать  ). Одно не понятно - критерий удачного маршрута. Что значит за минимальное время максимальное кол-во рабочих. Вот, например, можно минимизировать {время}/{количество рабочих} или {время} - {количество рабочих}. ИМХО необходимо формализовать оценку маршрута. 
ЗЫ 
Другое дело если под максимальным кол-вом рабочих имеется ввиду min{число мест в автобусе, общее кол-во ожидающих}. ..

ЗЫ ЗЫ 
 
 Да похоже это и нада..(сначала пример не прочитал). Ну, соответственно, оставляй тока не маршруты, где в конце число рабочих = min{число мест в автобусе, общее кол-во ожидающих}.


Это сообщение отредактировал(а) Sartorius - 16.12.2006, 16:31

максимальное количество рабочих - это:
*Вместимость автобуса, если вместимость автобуса <= общего числа рабочих
*Общее число рабочих, если вместимость автобуса > общего числа рабочих

Sartorius, спасибо, но нам сказали, что полным перебором считать нежелательно, надо искать алгоритм..((( Хотя мне кажется, придется все-таки перебирать... Только у меня проблема со считыванием данных из файла, нам это объяснили очень-очень плохо...

 Ну тада сведи к поиску минимального пути на графе (оценочная функция - время). При построении удаляй все пути глубины != максимальному числу рабочик.

спасибо, сейчас обдумаю...

Так, с вводом данных из файла пока можно подождать... интересует пока ПОДРОБНЫЙ алгоритм решения, не врубаюсь я никак..((( Точнее, постепенно врубаюсь, осталось совсем немного для полного понимания. Делаю по алгоритму, описанному здесь: http://g6prog.narod.ru/g6_1058.html.