记录编号	39169	评测结果	AAAAAAAAAA
题目名称	塔防游戏	最终得分	100
用户昵称	czp	是否通过	通过
代码语言	Pascal	运行时间	0.882 s
提交时间	2012-07-05 17:17:03	内存使用	15.64 MiB

var
 pa,c,lt,cc:array[0..1000,0..1011] of longint;
 l,d:array[0..1000] of longint;
 vh,h:array[0..1000] of longint;
 o:array[0..1000] of boolean;
 i,j,m,n,s,t,xx,yy,zz,k,flow,mf,kk:longint;
 oo:boolean;
procedure dfs(i:longint);
var mh,tp,j,l:longint;
begin
 tp:=mf;mh:=n-1;
 if i=t then begin inc(flow,mf);oo:=true;exit;end;
 for l:=1 to cc[i,0] do
   begin
   j:=cc[i,l];
   if c[i,j]>0 then
    begin
     if h[i]=h[j]+1 then
      begin
       if mf>c[i,j] then mf:=c[i,j];
       dfs(j);
       if h[s]>=n then exit;
       if oo then break;
       mf:=tp;
      end;
      if h[j]<mh then mh:=h[j];
    end;
   end;
  if not oo then
   begin
    dec(vh[h[i]]);
    if vh[h[i]]=0 then h[s]:=n;
    h[i]:=mh+1;
    inc(vh[h[i]]);
   end else begin
   inc(c[j,i]);
   dec(c[i,j]);end;
  end;
begin
 assign(input,'defence.in');reset(input);
 assign(output,'defence.out');rewrite(output);
 readln(n,m,s,t);
 fillchar(pa,sizeof(pa),$7f div 3);
 for i:=1 to m do
  begin
   readln(xx,yy,zz);
   pa[xx,yy]:=zz;
   pa[yy,xx]:=zz;
  end;
 fillchar(d,sizeof(d),$7f div 3);
 d[s]:=0;
 for i:=1 to n do
  begin
   k:=0;
   for j:=1 to n do if not o[j] then
    if d[j]<d[k] then k:=j;
   o[k]:=true;
   if k=0 then break;
   l[0]:=0;
   for j:=1 to n do
    if not o[j] then
     if d[k]+pa[k,j]<=d[j] then
       begin
         if d[k]+pa[k,j]<d[j] then
          begin
           for kk:=1 to lt[j,0] do c[lt[j,kk],j]:=0;
           lt[j,0]:=0;
           inc(l[0]);
           l[l[0]]:=j;
          end;
         if d[k]+pa[k,j]=d[j] then
          begin
           inc(l[0]);
           l[l[0]]:=j;
          end;
         d[j]:=d[k]+pa[k,j];
       end;
   for j:=1 to l[0] do
    begin
    c[k,l[j]]:=1;
    inc(lt[l[j],0]);
    lt[l[j],lt[l[j],0]]:=k;
    end;
  end;
  for i:=1 to n do
   for j:=1 to n do
    if  c[i,j]>0 then
     begin
      inc(cc[i,0]);
      cc[i,cc[i,0]]:=j;
      inc(cc[j,0]);
      cc[j,cc[j,0]]:=i;
     end;
 flow:=0;vh[0]:=n;
 while h[s]<n do
  begin
    oo:=false;
    mf:=maxlongint;
    dfs(s);
  end;
 writeln(flow);
 close(input);close(output);
end.