记录编号	2482	评测结果	AAAAAAAAAA
题目名称	找最佳通路	最终得分	100
用户昵称	MayLava	是否通过	通过
代码语言	Pascal	运行时间	0.003 s
提交时间	2008-09-21 20:46:23	内存使用	0.13 MiB

program MayLava;
var
 n,m,s,e,v:longint;
 map:array[1..100,0..100]of integer;
 dist:array[1..100]of longint;
 flag:array[1..100]of boolean;
procedure start;
 var
  f:text;
  i,x,y,z:longint;
 begin
  assign(f,'city.in');
  reset(f);
  readln(f,n,m,s,e);
  fillchar(map,sizeof(map),0);
  for i:=1 to m do begin
   readln(f,x,y);
   map[x,y]:=1;
  end;
 end;
procedure dijkstra;
 var
  i,j,k,a,max:longint;
 begin
  fillchar(dist,sizeof(dist),0);
  fillchar(flag,sizeof(flag),true);
  for i:=1 to n do begin
   dist[i]:=map[s,i];
  end;
  flag[s]:=false;
  for i:=1 to n do begin
   max:=maxint;
   for j:=1 to n do
    if flag[j] and (dist[j]<max) and (dist[j]>0) then begin max:=dist[j]; a:=j; end;
   flag[a]:=false;
   for k:=1 to n do
    if map[a,k]>0 then
     if (map[a,k]+dist[a]<dist[k]) or (flag[k] and (dist[k]=0)) then dist[k]:=map[a,k]+dist[a];
  end;
 end;
procedure print;
 var
  f:text;
 begin
  assign(f,'city.out');
  rewrite(f);
  writeln(f,dist[e]+1);
  close(f);
 end;
BEGIN
 start;
 dijkstra;
 print;
END.