Прошу помочь с задачей. Подскажите алгоритм (писать код не надо - если только не по собственно доброй воле).

Между N пунктами (N<=50) заданы дороги длиной A(i,j), где I,J-номера пунктов. Дороги проложены на разной высоте и пересекаются только в общих пунктах. В начальный момент времени из заданных пунктов начинают двигаться с постоянной скоростью M роботов (M=2 или 3), независимо меняя направление движения только в пунктах. Роботы управляются таким образом, чтобы минимизировать время до встречи всех роботов в одном месте(либо в городе, либо на дороге). Скорость I-того робота может быть равна 1 или 2. Остановка роботов запрещена.
Написать программу, которая при заданных N,M и сети дорог различной длины (все имеющиеся A(i,j)=разные) определяет минимальное время, через которое может произойти встреча всех M роботов, при этом начальное положение роботов и скорость их движения известны.
Примечание: В случае невозможности встречи всех M роботов в одном месте ни в какой момент времени в результате выполнения программы должно быть сформировано соответствующее сообщение.
Требование к вводу-выводу:
1) Все входные данные - целые неотрицательные числа;
2) при задании сети дорог должно быть указано количество дорог - K и пункты их начала и конца в виде пар (i,j).

Высказывайте все возможные предложения.

Это сообщение отредактировал(а) Codegrammer - 21.3.2009, 23:17

Если я правильно всё понимаю, то задача сводится к такой: для заданных вершин S[i] (i=1..M) и вершины T найти не обязательно простые пути S[i] -> T, такие, что длина каждого i-го пути, делённая на скорость i-го робота (1 или 2), получается одной и той же для всех путей (и наименьшей возможной).

Если бы мы заранее знали ещё и длину искомых путей, то можно было бы решать задачу независимо для всех роботов - просто проверить, что для i-го робота найдётся путь такой длины в графе, где все веса рёбер равны либо 1, либо 1/2 (в зависимости от скорости робота - 1 или 2 соответственно).

Поэтому я предлагаю искать кратчайшие пути (возможно, не простые) из каждой из вершин S[i] в вершину T, и искать среди них путь одной длины. Процесс этот представляет собой как бы метод движущихся указателей (для каждой из вершин S[i] ищем очередной кратчайший путь, среди найденных M путей удаляем кратчайший, и повторяем всё до тех пор, пока длины всех M путей окажутся одинаковыми).

Но решением это назвать довольно трудно - во-первых, для эффективной реализации (а, на мой взгляд, даже если ответ есть, то для него может понадобиться найти до N^M кратчайших путей) потребуется весьма нехилый алгоритм Эппштейна (я в своё время несколько дней понимал его, и потом полдня его писал и ещё день дебужил   ) (этот алгоритм в простейшем (но далеко не простом  ) варианте находит длины K кратчайших путей в графе с N вершинами и M рёбрами за O(M+NlogN+K) ).

Во-вторых, если ответа нет, то алгоритм этого никак не заметит, и будет бесконечно долго выуживать кратчайшие пути 

Добавлено через 6 минут и 6 секунд
Хотя, если предположение (скорее интуитивное) о достаточности N^M путей верно, то неограниченности не будет.

maxdiver, я прошу прощения за неясность в условии. Под словами "в одном месте" я понимал либо в городе, либо на дороге. Это сообщение уже отредактировано. Из-за этого ваш алгоритм не подойдет, хотя он довольно интересен.

А поясните тогда уж и фразу:

Означает ли это, что мы можем управлять роботами как хотим, или же они всегда ходят по кратчайшим путям?

Ну ладно, будем думать дальше 

Это означает, что путь до встречи их в одном месте является кратчайшим. Т.е. при меньшем пути они никогда не встретятся в одной точке. Если рассматривать этот же путь, не принимая во внимание других роботов, то вполне может быть, что он и не кратчайший.

на мой взгляд, здесь нужно употребить динамическое программирование

Это зависит от ограничений на длины дорог. Динамика ведь разве что по текущей длине пути, да? Если Aij и правда не очень большие, то можно попробовать этот вариант.

В задаче на это ограничения нет. Ну а если бы было, то как динамикой? 

d[i][v][l] - можно ли i-ым роботом прийти в вершину v за время l.

если найдётся такое v0 и l0, что d[i][v0][l0] = true для всех i, то можно встретиться в этой вершине.

если найдётся такое ребро (a,b) длины len и такое l и такое 0<k<len, что для всех i выполняется: d[i][a][l-k/speed[i]] || d[i][b][l-(len-k)/speed[i]], т.е. они могут встретиться в момент времени l в позиции k на этом ребре, то ответ тоже true.

ну понятно, что при больших длинах рёбер это всё будет работать страшно медленно.

как считать саму динамику d[i][v][l] - думаю, понятно. пробегаемся по всём рёбрам из v, и если хотя бы по одному из рёбер оказалось d[i][edge_v][l-edge_len] = true, то и d[i][v][l] = true.

Довольно интересный подход. Но здесь вы не учитываете, встреча может произойти не обязательно в целочисленный момент времени.

Ну учитывая, что все скорости равны 1 или 2, то мы все длины можем увеличить в 2 раза, за счёт этого времена прихода роботов в вершины уже станут целыми (ну или просто, ничего не удлиняя, а помня, что все времена - целые или полуцелые).

А встречи в серединах рёбер - по моим выкладкам получается, что два робота, если имеют разные скорости, могут встретиться либо в полуцелые, либо в шестьцелые (сам сейчас придумал  ну вида k/6) моменты времени. Я записал уравнение встречи для двух роботов разных скоростей:
x + 2y = len (это если с разных концов навстречу идут),
или x = 2y (если с одного конца)
и всё при условии a+x = b+y.
Здесь a и b - времена прихода роботов в вершины-концы рёбер, x и y - времена их движения по ребру.
Если мы их разрешим, в первом случае получится вида x=целое/3, во втором - x=целое, и в обоих - y=x+целое/2. Итого y может быть целое/6, и это наихудший случай.

Если два робота имеют одинаковую скорость (понятно, нам хуже всего, когда =2), то получаются "четверть-целые" времена в худшем случае 

Ну это и интуитивно было понятно, что при таких скоростях все времена будут "не сильно" дробными.

Это сообщение отредактировал(а) maxdiver - 28.3.2009, 19:24

Ну кстати, вот это уже дело. Т.е получается берем НОК(4,6)=12. Умножаем ребра на 12. Применяем динамику. Делим t на 12 и все. Классно придумал. Огромное спасибо!!