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

program defence;
var
  d,link:array[1..1000,0..1000] of longint;
  c:array[1..1000,1..1000] of boolean;
  dis:array[1..1000] of longint;
  ina:array[1..1000] of boolean;
  gap,height,now:array[0..1000] of longint;
  n,i,j,k,l,m,s,t,mini,maxflow,minh,minE:longint;
  find:boolean;
procedure search(v:longint);
  var
    i:longint;
  begin
    ina[v]:=true;
    for i:=1 to n do
      if dis[v]+d[v,i]=dis[i] then begin
         c[v,i]:=true;
         inc(link[v][0]);
         link[v][link[v][0]]:=i;
         inc(link[i][0]);
         link[i][link[i][0]]:=v;
         if not ina[i] then search(i);
      end;
  end;
procedure SAP(k:longint);
  var
    x:longint;
  begin
    if k=t then begin
      find:=true;inc(maxflow);exit;
    end;
    while now[k]<=link[k][0] do begin
      x:=link[k][now[k]];
      if c[k,x] and (height[k]=height[x]+1) then begin
        SAP(x);
        if height[s]=n then exit;
        if find then break;
      end;
      inc(now[k]);
    end;
    if find then begin
      c[k,x]:=false;
      c[x,k]:=true;
    end else begin
      minh:=n-1; minE:=1;
      for i:=1 to link[k][0] do
        if c[k,link[k][i]] and (height[link[k][i]]<minh) then begin
          minE:=i; minh:=height[link[k][i]];
        end;
      dec(gap[height[k]]);
      if gap[height[k]]=0 then height[s]:=n;
      height[k]:=minh+1;  now[k]:=minE;
      inc(gap[minh+1]);
    end;
  end;
begin
  assign(input,'defence.in');reset(input);
  assign(output,'defence.out');rewrite(output);
  // input
  readln(n,m,s,t);
  filldword(d,sizeof(d)>>2,maxlongint>>2);
  //for i:=1 to n do d[i,i]:=0;
  for l:=1 to m do begin
    readln(i,j,d[i,j]);
    d[j,i]:=d[i,j];
  end;
  //  Dijkstra
  for i:=1 to n do dis[i]:=maxlongint>>2;
  dis[s]:=0;  l:=0;
  repeat
    inc(l); mini:=maxlongint; k:=0;
    for i:=1 to n do
      if not ina[i] and (dis[i]<mini) then begin
        k:=i;mini:=dis[i];
      end;
    ina[k]:=true;
    for i:=1 to n do
      if not ina[i] and (dis[k]+d[k,i]<dis[i]) then
        dis[i]:=dis[k]+d[k,i];
  until l=n;
  //  Build Graph
  fillchar(ina,sizeof(ina),false);
  search(s);
  //for i:=1 to n do c[i,i]:=false;
  //  SAP
  for i:=1 to n do now[i]:=1;
  gap[0]:=n;
  repeat
    find:=false;
    SAP(s);
  until height[s]=n;
  //  Print
  writeln(maxflow);
  close(input); close(output);
end.