Между N пунктами (N≤50) заданы дороги длиной A(i,j), где i, j - номера пунктов. Дороги проложены на разной высоте и пересекаются только в общих пунктах. В начальный момент времени из заданных пунктов начинают двигаться с постоянной скоростью M роботов (M равно 2 или 3), независимо меняя направление движения только в пунктах. Роботы управляются таким образом, чтобы минимизировать время до встречи всех роботов в одном месте. Скорость i-го робота может быть равна 1 или 2. Остановка роботов запрещена.
Длины дорог задаются...

Честно говоря, без примитивного графического представления задачи разобратся с условием немогу.
И в чем заключается задание?

как найти вершину, равноудаленную от 3-х вершин?

Если не ошибаюсь, то строишь по 3 вершинам треугольник, к двум из граней проводишь серединный перпендикуляр. На их пересечении будет равноудаленная от 3 вершин точка, а вообще все три серединных перпендикуляра будут пересекаться в одной точке.

хм...какие перпендикуляры в графах????

Jilian какие графы, я о треугольниках говорил.
Ты бы сам сначала говорил, что о графах. Для твоего случая задача комивояжера случайно не подойдет?

Вай, во-первых, не говорил, а говорилА. Во-вторых, при чем же тут треугольники? -)))
Нет, задача комивояжера не пройдет.

1. Пункты соединяются каждый с каждым?
2. Место встречи может быть посередине дороги или только в пунктах?
3. Можно ли возращаться в пункты в которых уже был? Ходить по дорогам, по которым уже ходил?
4. Скорость у роботов фиксирована на всё время движения, или меняется от пункта к пункту?

Попробуй сгенерировать новый граф, на нём найти длины путей, пропорциональные как раз времени. Можно ещё использовать полный перебор, но сложность будет более чем O(n^2) это точно. задача не из простых. Не знаю прокатит ли тут это, раз уж речь идёт о графах, то нужно тыкаться в известные популярные алгоритмы на графах, эту задачу можно к ним свести я так думаю.

Jilian
Я что-то не понял, граф полносвязный или нет? Что значит встретятся в одном месте? То есть для начала надо определить населенный пункт, в который все M штук могут попасть за наименьшее время?
Вообще было бы очень не плохо если бы Вы рисунок нарисовали, ну хоть какой-нибудь.

Если граф не связный - роботы не встретятся Думаю что имелось ввиду 1 место - 1 вершина.

Это возможно не во всех случаях. Если строить не оптимальный, а какой-нибудь, то понятно: берём любые маршруты к одной вершине. Потом у нас появляется возможность их удлинять за счёт добавления циклов/хождения взад-вперёд по ребру. Для каждого из маршрутов составляем список, на сколько можем его продлить. Ну и дальше всякие штуки с НОД и НОК - подбирается, сколько к какому маршруту добавить.

Но для оптимального перебор получается внушительный...

Всем спасибо! Задачу я уже решила и сдала.