记录编号	39214	评测结果	AAAAAAAAAA
题目名称	塔防游戏	最终得分	100
用户昵称	isabella	是否通过	通过
代码语言	Pascal	运行时间	0.612 s
提交时间	2012-07-06 21:16:01	内存使用	12.59 MiB

var
 i,j,n,m,minh,ans,p,b,x,head,tail,s,t:longint;
 a,d:array[1..1000]of longint;
 v:array[1..1000]of boolean;
 map,w,c:array[1..1000,0..1000]of longint;
 co:array[1..1000,1..1000]of boolean;
 gap,h:array[0..1000]of longint;
 flag:boolean;
  
 procedure spfa;
  var i:longint;
  begin
    head:=0;tail:=1;a[1]:=s;
    fillchar(v,sizeof(v),0);v[s]:=true;
    fillchar(d,sizeof(d),$3f);d[s]:=0;
    repeat
       head:=(head mod n)+1;
       x:=a[head];
       for i:=1 to map[x,0] do
         if (d[x]+w[x,i]<d[map[x,i]])then
             begin
                d[map[x,i]]:=d[x]+w[x,i];
                if v[map[x,i]]=false then
                   begin
                      tail:=(tail mod n)+1;
                      a[tail]:=map[x,i];v[map[x,i]]:=true; 
                   end;
             end;
        v[x]:=false;       
    until head=tail;
  end;
  
 function min(a,b:longint):longint;
   begin if a<b then exit(a) else exit(b);end;
       
 procedure sap(k:longint);
  var i,minh,j,p:longint;
  begin
    if k=t then
         begin
            ans:=ans+1;
            flag:=true;exit;
         end;
    minh:=n-1;
    for i:=1 to c[k,0] do
      begin
        j:=c[k,i]; 
        if co[k,j] then
            begin
		    // minh:=min(minh,h[j]);	
              if h[j]+1=h[k] then
                  begin
                     sap(j); 
			         if h[s]>=n then exit;
                     if flag then break;
                  end ;
			  minh:=min(minh,h[j]);	
            end;
			 
      end;          
     if flag then begin
            co[k,j]:=false;co[j,k]:=true;
            inc(c[j,0]);c[j,c[j,0]]:=k;
      end else begin
            dec(gap[h[k]]);
            if gap[h[k]]=0 then h[s]:=n;
            h[k]:=minh+1;
            inc(gap[h[k]]);
      end ;  
  end; 
  
begin
assign(input,'defence.in');reset(input);
assign(output,'defence.out');rewrite(output);
  readln(n,m,s,t);
  fillchar(co,sizeof(co),0);
  fillchar(c,sizeof(c),0);
  fillchar(map,sizeof(map),0);
  fillchar(w,sizeof(w),0);         
  for i:=1 to m do
    begin
      readln(p,b,j);
      inc(map[p,0]);map[p,map[p,0]]:=b;w[p,map[p,0]]:=j;
      inc(map[b,0]);map[b,map[b,0]]:=p;w[b,map[b,0]]:=j;
    end;
   
  spfa;
  for i:=1 to n do
    for j:=1 to map[i,0] do
      if d[i]+w[i,j]=d[map[i,j]]then
           begin
             inc(c[i,0]);c[i,c[i,0]]:=map[i,j];co[i,map[i,j]]:=true;
           end ;
  gap[0]:=n;
  ans:=0;
  while h[s]<>n do
     begin
        flag:=false;
        sap(s);
     end;
   writeln(ans);
 close(input);close(output)
end.