Advertisement
savrasov

bfs

Jan 4th, 2017
398
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Delphi 1.35 KB | None | 0 0
  1. type
  2.   triplet = record
  3.     u, pr, v: integer;
  4.   end;
  5.  
  6. var
  7.   list, head, next, a, b, vv: array [1..2500000] of integer;
  8.   joo: array [0..9000000] of triplet;
  9.   i, h, f, m, n, u, uu, ish, beg, en: integer;
  10.  
  11. procedure push(a, b: integer);
  12. begin
  13.   inc(h);
  14.   list[h] := b;
  15.   next[h] := head[a];
  16.   head[a] := h;
  17. end;
  18.  
  19. procedure push1(u, pr, v: integer);
  20. begin
  21.   en := (en + 1) mod 9000000;
  22.   joo[en].u := u;
  23.   joo[en].pr := pr;
  24.   joo[en].v := v;
  25. end;
  26.  
  27. function min(a, b: integer): integer;
  28. begin
  29.   if a < b then min := a
  30.   else min := b;
  31. end;
  32.  
  33. procedure bfs();
  34. var
  35.   u, pr, v: integer;
  36. begin
  37.   while (beg <> en) do
  38.   begin
  39.     beg := (beg + 1) mod 9000000;
  40.     u := joo[beg].u;
  41.     pr := joo[beg].pr;
  42.     v := joo[beg].v;
  43.     b[u] := pr;
  44.     vv[u] := v;
  45.     u := head[u];
  46.     while (u <> 0) and ((v + 1) * 2 + 1 < f) do
  47.     begin
  48.       if (b[list[u]] <> pr) and (b[list[u]] <> 0) then f := min(f, v + 1 + vv[list[u]])
  49.       else if (b[list[u]] = 0) then push1(list[u], pr, v + 1);
  50.       u := next[u];
  51.     end;
  52.   end;
  53. end;
  54.  
  55. begin
  56.   readln(n, m);
  57.   h := 0;
  58.   beg := 0;
  59.   en := 0;
  60.   for i := 1 to n do read(a[i]);
  61.   for i := 1 to m do
  62.   begin
  63.     readln(u, uu);
  64.     push(u, uu);
  65.     push(uu, u);
  66.   end;
  67.   f := m + 2;
  68.   for ish := 1 to n do
  69.     if (a[ish] <> 0) then
  70.       push1(ish, a[ish], 0);
  71.   bfs;
  72.   writeln(f);
  73. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement