fork download
copy 
  1. const maxn = 250;
  2.       oo = 60000;
  3.       maxq = 1000000;
  4. type tqueue = record
  5.                 front,rear,nitem:longint;
  6.                 itemx,itemy,itemz: array[0..maxq-1] of byte;
  7.               end;
  8. var n,s,t:byte;
  9.     m:word;
  10.     g: array[1..maxn,0..maxn] of byte;
  11.     dp: array[1..maxn,1..maxn,0..1] of word;
  12.     queue: tqueue;
  13. procedure initq;
  14. begin
  15.   with queue do
  16.   begin
  17.     nitem:=0;
  18.     front:=0; 
  19.     rear:=1;
  20.   end;
  21. end;
  22. function empty:boolean;
  23. begin
  24.   with queue do
  25.   empty:=(nitem=0);
  26. end;
  27. procedure push(x,y,z:byte);
  28. begin
  29.   with queue do
  30.   begin
  31.     front:=(front+1) mod maxq;
  32.     inc(nitem);
  33.     itemx[front]:=x;
  34.     itemy[front]:=y; 
  35.     itemz[front]:=z;
  36.   end;
  37. end;
  38. procedure pop(var x,y,z:byte);
  39. begin
  40.   with queue do
  41.   begin
  42.     dec(nitem);
  43.     x:=itemx[rear];
  44.     y:=itemy[rear]; 
  45.     z:=itemz[rear];
  46.     rear:=(rear+1) mod maxq;
  47.   end;
  48. end;
  49. procedure enter;
  50. var i:word;
  51.     u,v,j,z:byte;
  52. begin
  53.   readln(n,m);
  54.   readln(s,t);
  55.   for i:=1 to n do
  56.   g[i,0]:=0;
  57.   for i:=1 to m do
  58.   begin
  59.     readln(u,v);
  60.     inc(g[u,0]);
  61.     g[u,g[u,0]]:=v;
  62.   end;
  63.   for i:=1 to n do
  64.   for j:=1 to n do
  65.   for z:=0 to 1 do
  66.   dp[i,j,z]:=oo;
  67.   dp[s,t,1]:=0;
  68.   initq;
  69.   push(s,t,1);
  70. end;
  71. procedure bfs;
  72. var x,y,z,i:byte;
  73.     mind: word;
  74. begin
  75.   repeat
  76.     pop(x,y,z);
  77.     if (z=0) then
  78.     begin
  79.       for i:=1 to g[x,0] do
  80.       if dp[x,y,z]+1<dp[g[x,i],y,1] then
  81.       begin
  82.         dp[g[x,i],y,1]:=dp[x,y,z]+1;
  83.         push(g[x,i],y,1);
  84.       end;
  85.     end
  86.     else
  87.     begin
  88.       for i:=1 to g[y,0] do
  89.       if dp[x,y,z]+1<dp[x,g[y,i],0] then
  90.       begin
  91.         dp[x,g[y,i],0]:=dp[x,y,z]+1;
  92.         push(x,g[y,i],0);
  93.       end;
  94.     end;
  95.   until empty;
  96.   mind:=oo;
  97.   for i:=1 to n do
  98.   if dp[i,i,1]<mind then mind:=dp[i,i,1];
  99.   if mind=oo then writeln(-1) else writeln(mind div 2);
  100. end;
  101. begin
  102.   enter;
  103.   bfs;
  104. end.
Success #stdin #stdout 0s 3512KB
comments (?)
stdin
copy 
6 7
1 5
1 2
4 5
2 3
3 4
4 1
5 4
5 6
stdout
copy 
3
https://ideone.com/HUl3ZU
language:
Pascal (fpc 3.0.4)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!