Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Роботы

Автор: Nezhny_Vampir 12.11.2006 21:43

Цитата
В подземелье есть N залов, соединенных туннелями. В некоторых залах находятся роботы, которые одновременно получили команду собраться в одном месте.
Роботы устроены так, что, получив команду, они все начали двигаться с такой скоростью, что туннель между двумя любыми залами преодолевают за 1 минуту. Роботы не могут останавливаться (в том числе и в залах), а также менять направление движения, находясь в туннелях (однако попав в зал робот может из него пойти по тому же туннелю, по которому он пришел в этот зал).
Напишите программу, вычисляющую, через какое минимальное время все роботы смогут собраться вместе (в зале или в туннеле).
Формат входных данных
Во входном файле записаны сначала числа N — количество залов (1N400) и K — количество туннелей (1K20000). Далее записано K пар чисел, каждая пара описывает номера залов, соединяемых туннелем (по туннелю можно перемещаться в обе стороны). Между двумя залами возможно несколько туннелей. Туннель может соединять зал с самим собой. Далее записано число M (1M400) — количество роботов. Затем идет M чисел, задающих номера залов, где вначале расположены роботы. В одном зале может быть несколько роботов.
Формат выходных данных
В выходной файл выведите минимальное время в минутах, через которое роботы могут собраться вместе. Если роботы никогда не смогут собраться вместе, выведите одно число –1 (минус один).
Примеры
f.in
f.out
4 5
1 2
2 3
3 4
1 4
1 3
3
1 2 4
1
3 3
1 2
2 3
3 1
3
1 2 3
1.5


В какую сторону двигаться?

А еще, где можно взять решения задач с IX Московской командной олимпиады школьников по программированию (проходившей в 2005 году)?

Автор: мисс_граффити 12.11.2006 21:50

а как считать время, если они собрались в туннеле?.. Ну, собственно, не в этом счастье...
Это школьно-олимпиадная задача? Пока мысли в сторону построения графа (даже не столько графа как динамической структуры, сколько задающей его матрицы смежности вершин) и поиска кратчайшего пути в нем - понятно, что искомое время равно времени, которое потратит самый дальний робот....