Метод Дейкстра, применяется для
*поиска кратчайших расстояний от одной вершины до всех остальных
*построения оптимальных маршрутов от одной вершины до всех остальных
Задача "Пирамида Хеопса" (Автор - Котов В.М.)
Республиканская олимпиада по информатике 1996г
Внутри пирамиды Хеопса есть N комнат, в которых установлены 2М модулей, составляющих М устройств. каждое устройство состоит из двух модулей, которые располагаются в разных комнатах, и предназначено для перемещения между парой комнат, в которых установлены эти модули. Перемещение происходит за 0.5 условных единицы времени. В начальный момент времени модули всех устройств переходят в "подготовительный режим". Каждый из модулей имеет некоторый свой целочисленный период времени, в течение которого он находится в "подготовительном режиме". По истечении этого времени модуль мгоновенно "срабатывает" после чего опять переходит в "подготовительный режим". Устройством можно воспользоваться только в тот момент, когда одновременно "срабатывают" оба его модуля.
Индиана Джонс сумел проникнуть в гробницу фараона (комната 1). Обследовав ее, он включил устройства и собрался уходить, но в этот момент проснулся хранитель гробницы. Теперь Джонсу необходимо как можно быстрее попасть в комнату N, в которой находится выход из пирамиды. При этом из комнаты в комнату он может попадать только при помощи устройств, так как проснувшийся хранитель закрыл все двери в комнатах пирамиды.
Необходимо написать программу, которая получает на входе описания расположения устройств и их характеристик (смотри описание формата ввода), а выдает значение оптимального времени и последовательность устройств, которыми надо воспользоваться, что бы попасть из комнаты 1 в комнату N за это время.
Входной файл: input2.txt Выходной файл: output2.txt
Формат ввода:
N
M
R11 T11 R12 T12
...
RM1 TM1 RM2 TM2
где
N (2<=N<=100) - количество комнат
M (M<=100) - количество устройств
Ri1 и Ri2 - номера комнат, в которых располагаются модули устройства i
Ti1, Ti2 (Ti1,Ti2<=1000) - периоды времени, через которые срабатывают эти модули
Все числа - натуральные.
Пример
4
5
1 5 3 2
1 1 2 1
2 5 3 5
4 4 3 2
3 5 4 5
Оптимальное время: 8.5
искомая последовательность: 2 3 4
Кратко алгоритм решения может быть изложен следующим образом.
Представив комнаты - вершинами, а пары устройств (с временами срабатывания) - взвешенными дугами,
можем применить алгоритм Дейкстра для поиска кратчайшего пути от первой вершины до последней. Точнее, алгоритм Дейкстра построит кратчайшие пути от первой до всех остальных, но в данной задаче нас интересует только кратчайший путь от первой до последней.
Нужно учитывать, что дуги существуют только в моменты, кратные временам срабатывания.
Рассмотрим решение более подробно.
Ввод исходных данных :
read(N,M); for I:=1 to N do kG[i]:=0;
for i:=1 to M do
begin
read(r1,t1,r2,t2);
nok:= (t1*t2) div Nod(t1,t2); {nok - наименьшее общее кратное}
{Nod-наибольший общий делитель }
{ чисел t1 и t2 }
inc(kG[r1]); G[r1,kg[r1]]:=r2; P[r1,kg[r1]]:=nok;
inc(kG[r2]); G[r2,kg[r2]]:=r1; P[r2,kg[r2]]:=nok;
end;Исходный граф по условиям задачи неориентированный. Поэтому мы вводим обе дуги. При этом граф представляется в виде списка дуг смежных с текущей: kG[i] - количество дуг из вершины i
G[i,j] - вершина, в которую из вершины i идет дуга под порядковым номером j
P[i,j] - вес дуги из вершины i вершину G[i,j]
Для вычисления nod используется функция, основанная на алгоритме Евклида:
function Nod (a,b:longint):longint;
begin
while (a<>b) do if a>b then a:=a-b else b:=b-a;
Nod:=a;
end;Затем проводится подготовка к выполнению алгоритма Дейкстры:
for i:=1 to N do { Для всех вершин }
begin
Labl[i]:=FREE; { Помечаем как свободную }
pred[i]:=1; { Предок - первая }
d[i]:=maxlongint; { Расстояние до первой - маx }
end;
Labl[1]:=DONE; { Первая - обработана }
Pred[1]:=0; { Предок у первой - 0 }
d[1]:=0; { Расстояние от первой до первой - 0 }
for j:=1 to kG[1] do { Для всех дуг из первого ребра }
d[G[1,j]]:=P[1,j]+0.5; { Расстояние до первой вершины }
{ равно весу ребра + 0.5 }Заметим, что в последней строке к весу ребер добавляется 0.5, поскольку по условиям задачи перемещение с помощью устройств из одной комнаты в другую занимает 0.5 единицы времени.
Далее идет основной цикл алгоритма Дейкстра
for i:=1 to N-1 do
begin
Поиск ближайшей к первой вершине из необработанных
Пересчет кратчайших расстояний через ближайшую вершину
до вершин, смежных с ближайшей
end;Первый этап - "Поиск ближайшей к первой вершине из необработанных"
MinD:=maxlongint; { MinD - max }
for j:=1 to N do { Для всех вершин }
if (Labl[j]=FREE) { если вершина свободна }
and (d[j]<MinD) { и расстояние от нее до первой }
{ вершины меньше MinD }
then
begin
MinD:=d[j]; { Заносим это расстояние в MinD }
Bliz:=j { Вершину запоминаем как ближайшую }
end;
Labl[Bliz]:=DONE; { Найденную ближайшую помечаем }
{ как обработанную }Второй этап - "Пересчет кратчайших расстояний через ближайшую вершину до вершин, смежных с ближайшей"
for j:=1 to kG[Bliz] do { Для всех вершин смежных с ближайшей}
if (Labl[G[Bliz,j]]=FREE) {Если вершина еще не обрабатывалась }
then
begin
NewTime:=Calculat(d[bliz],P[bliz,j]); {Вычислитьрасстояниедонее}
{в терминах задачи-время }
{перемешения в нее }
if d[G[Bliz,j]]> NewTime +0.5 {Если новое время лучше }
then
begin
d[G[Bliz,j]]:= NewTime+0.5; {заносим его в массив D }
pred[G[Bliz,j]]:=Bliz; {указываем ближайшую как }
end; {предыдущую для текущей }
end;При вычислении кратчайшего расстояния до текущей вершины через ближайшую (в терминах алгоритма Дейкстра) или времени перемещения из первой комнаты через ближашую в текущую (в терминах данной задачи)
используется функция Calculat (T,Tnok):
function Calculat (T:single; Tnok:longint):longint;
var i : longint;
begin
TRes:=0;
while (T>TRes) do inc(TRes,Tnok);
Calculat:=TRes ;
end;Эта функция вычисляет время TRes (которое передается в вызывающую программу непосредственно через имя функции Calculat), ближайшее большее текущего времени T (T равно минимальному значению времени, которое потребовалось, что бы оптимальным образом добраться из первой вершины до ближайшей вершины) и кратное Tnok - периоду срабатывания пары устройств, связывающих комнаты Bliz (ближайшая) и G[Bliz,j] (текущая).
После выполнения алгоритма Дейкстра сформированы массивы
d[j] - кратчайшее расстояние от начальной вершины до вершины j
pred[j] - предок вершины j на оптимальном маршруте
По этой информации вывод результата осуществляется следующим образом:
tg:=N; i:=0; { Начиная с последней вершины }
while tg<>0 do { Пока не закончились предшествующие }
begin
inc(i); { Инкрементируем количество вершин в пути }
path[i]:=tg; { Заносим текущую в массив пути }
tg:=pred[tg]; { Переустанавливаем предыдущую }
end;
writeln('Оптимальное время: ',D[N]:0:1);
write('искомая последовательность:');
for j:=i-1 downto 1 do write(' ',path[j]);Ниже приведен полный текст решения задачи.
{$R+,E+,N+}
program by96d1s2;
const
FREE=1;
DONE=2;
var
G : array[1..100,1..100] of byte;
P : array[1..100,1..100] of longint;
D : array[1..100] of single;
Labl,pred,kG : array[1..100] of byte;
path : array[1..100] of byte;
is,t1,t2,nok,Tres,NewTime : longint;
i,j,x,y,A,B,C,N,M,tg,Bliz : byte;
r1,r2 : byte;
Yes : boolean;
MinD : single;
function Nod (a,b:longint):longint;
begin
while (a<>b) do
if a>b then a:=a-b else b:=b-a;
Nod:=a;
end;
function Calculat (T:single; Tnok:longint):longint;
var i : longint;
begin
TRes:=0;
while (T>TRes) do inc(Tres,Tnok);
Calculat:=TRes ;
end;
begin
assign(input,'input2.txt'); reset(input);
assign(output,'output2.txt'); rewrite(output);
read(N,M);
for I:=1 to N do kG[i]:=0;
for i:=1 to M do
begin
read(r1,t1,r2,t2); nok:= (t1*t2) div Nod(t1,t2);
inc(kG[r1]); G[r1,kg[r1]]:=r2; P[r1,kg[r1]]:=nok;
inc(kG[r2]); G[r2,kg[r2]]:=r1; P[r2,kg[r2]]:=nok;
end;
for i:=1 to N do
begin
Labl[i]:=FREE; pred[i]:=1; d[i]:=maxlongint;
end;
Labl[1]:=DONE; Pred[1]:=0; d[1]:=0;
for j:=1 to kG[1] do d[G[1,j]]:=P[1,j]+0.5;
for i:=1 to N-1 do
begin
MinD:=maxlongint;
for j:=1 to N do
if (Labl[j]=FREE) and (d[j]<MinD)
then begin MinD:=d[j]; Bliz:=j end;
Labl[Bliz]:=DONE;
for j:=1 to kG[Bliz] do
if (Labl[G[Bliz,j]]=FREE)
then begin
NewTime:=Calculat(d[bliz],P[bliz,j]);
if d[G[Bliz,j]]> NewTime +0.5
then
begin
d[G[Bliz,j]]:= NewTime+0.5;
pred[G[Bliz,j]]:=Bliz;
end;
end;
end;
tg:=N; i:=0;
while tg<>0 do
begin
inc(i); path[i]:=tg; tg:=pred[tg];
end;
writeln('Оптимальное время: ',D[N]:0:1);
write('искомая последовательность:');
for j:=i-1 downto 1 do write(' ',path[j]);
close(input); close(output);
end.
