Warning: Illegal string offset 'html' in /var/www/lvp37/data/www/lvp37.ru/cache/skin_cache/cacheid_2/skin_topic.php on line 414
Поиск в ширину - олимпиадники-информатики
←  Графы

олимпиадники-информатики

»

Поиск в ширину

Санек фотография Санек 21 Dec 2011

Поиск в ширину, применяется для решения произвольных задач на графах, требующих соответствующего порядка обхода ("в ширину") графа; раскрашивая пройденные вершины и/или дуги можно управлять порядком и способами обхода (например, однократное или многократное использование дуг и вершин)

Задача Кратчайший маршрут


В стране Б есть N городов, которые соединены M дорогами. По дорогам можно ездить в обоих направлениях. Между двумя городами могут существовать несколько дорог. Мальчик Вася живет в городе с номером 1, и он хочет поехать в город с номером N. Система дорог спроектирована так, что время проезда по каждой дороге одинаковое. Вася просит вас помочь найти кратчайший маршрут из города 1 в город N. Для этого вам необходимо выяснить, какое минимальное количество дорог необходимо проехать, чтобы попасть в желаемый город.
Формат ввода:
N M
X[1] Y[1]
X[2] Y[2]

X[M] Y[M]
N – количество городов в стране.
M – количество дорог в стране.
X[i] Y[i] – описание i-ой дороги между городами X и Y.
Ограничения:
2 <= N < = 1000
1 <= M < = 2000
Формат вывода:
Ответ на задачу - минимальное количество дорог, которые необходимо проехать, чтобы попасть в желаемый город.
Пример ввода:
4 4
1 2
2 3
2 4
3 4
Пример вывода:
2

var g:array[1..1000,1..1000] of longint; p,q:array [1..1000] of longint;  i,uk,un,n,m,a,b,v:longint;
begin
 readln(n,m);
 for i:=1 to m do
  begin
   readln(a,B)/>;
   g[a,b]:=g[a,b]+1;
   g[b,a]:=g[b,a]+1;     
  end;
 for i:=1 to n do
  begin
   p[i]:=-1;
   g[i,i]:=0;
  end;
 un:=1;
 uk:=2;
 p[1]:=0;
 q[1]:=1;
 while uk<>un do
  begin
   v:=q[un];
   un:=un+1;
   for i:=1 to n do
    if (g[v,i]>0)and(p[i]=-1) then begin
                                    q[uk]:=i;
                                    uk:=uk+1;
                                    p[i]:=p[v]+1;
                                   end;
  end;
 writeln(p[n]);
end.
Ответить