记录编号	39180	评测结果	AAWAAWAAAA
题目名称	塔防游戏	最终得分	80
用户昵称	wo shi 刘畅	是否通过	未通过
代码语言	Pascal	运行时间	0.615 s
提交时间	2012-07-05 18:03:00	内存使用	30.82 MiB

var
  n,m,s,tt,ans,total,i,j,x,y,z:longint;
  last,d,first:array[0..10000]of longint;
  value,point,next,eq,p,q:array[0..1000000]of longint;
  v:array[0..10000]of boolean;
  g,b:array[0..1000,0..1000]of longint;

procedure spfa;
var
  i,h,t,x,y:longint;
begin
  h:=1;
  t:=1;
  q[1]:=s;
  for i:=1 to n do d[i]:=maxlongint div 2;
  d[s]:=0;
  for i:=1 to n do v[i]:=false;
  v[s]:=true;
  repeat
    x:=q[h];
    for i:=1 to n do
    begin
      if d[x]+g[x,i]<d[i] then
      begin
        d[i]:=d[x]+g[x,i];
        b[i,0]:=1;
        b[i,1]:=x;
        if not v[i] then
        begin
          v[i]:=true;
          inc(t);
          q[t]:=i;
        end;
      end
      else if d[i]=d[x]+g[x,i] then
      begin
        inc(b[i,0]);
        b[i,b[i,0]]:=x;
      end;
    end;
    v[x]:=false;
    inc(h);
  until h>t;
end;

procedure build(x,y,z,k:longint);
begin
  inc(total);
  point[total]:=y;
  value[total]:=z;
  p[total]:=total+k;
  next[total]:=first[x];
  first[x]:=total;
end;

procedure change(x,y,z:longint);
begin
  build(x,y,z,1);
  build(y,x,z,0);
end;

function bfs:boolean;
var
  h,t,i,x,y:longint;
begin
  for i:=1 to n do d[i]:=-1;
  d[s]:=0;
  h:=1;
  t:=1;
  q[1]:=s;
  repeat
    x:=q[h];
    i:=first[x];
    while i>0 do
    begin
      y:=point[i];
      if (d[y]=-1)and(value[i]>0) then
      begin
        inc(t);
        q[t]:=y;
        d[y]:=d[x]+1;
        if y=tt then exit(true);
      end;
      i:=next[i];
    end;
    inc(h);
  until h>t;
  exit(false);
end;

procedure dfs;
var
  top,i,x,y,j:longint;
begin
  for i:=1 to n do last[i]:=first[i];
  top:=1;
  q[1]:=s;
  while top>0 do
  begin
    x:=q[top];
    if x<>tt then
    begin
      i:=last[x];
      while i>0 do
      begin
        y:=point[i];
        if (d[y]=d[x]+1)and(value[i]>0) then break;
        i:=next[i];
      end;
      if i<>0 then
      begin
        inc(top);
        q[top]:=y;
        eq[top]:=i;
      end
      else begin
        dec(top);
        d[x]:=-1;
      end;
    end
    else begin
      j:=maxlongint;
      for i:=2 to top do if value[eq[i]]<j then j:=value[eq[i]];
      for i:=2 to top do
      begin
        dec(value[eq[i]],j);
        inc(value[p[eq[i]]],j);
      end;
      inc(ans,j);
      i:=2;
      while value[eq[i]]>0 do inc(i);
      top:=i-1;
    end;
  end;
end;

procedure maxflow;
var
  i,t,h,x:longint;
begin
  t:=s;
  s:=tt;
  tt:=t;
 { h:=1;
  t:=1;
  q[1]:=s;
  for i:=1 to n do v[i]:=false;
  v[s]:=true;
  repeat
    x:=q[h];
    for i:=1 to b[x,0] do
    if not v[b[x,i]] then
    begin
      change(x,b[x,i],1);
      v[b[x,i]]:=true;
      inc(t);
      q[t]:=b[x,i];
    end;
    inc(h);
  until h>t;  }
  for i:=1 to n do
  begin
   for j:=1 to b[i,0] do
   begin
     change(i,b[i,j],1);
  //   write(b[i,j],' ');
   end;
//   writeln;
  end;
  ans:=0;
  while bfs do dfs;
  writeln(ans);
end;

begin
  assign(input,'defence.in'); reset(input);
  assign(output,'defence.out'); rewrite(output);
  read(n,m,s,tt);
  for i:=1 to n do
   for j:=1 to n do
   g[i,j]:=maxlongint div 2;
  for i:=1 to m do
  begin
    read(x,y,z);
    g[x,y]:=z;
    g[y,x]:=z;
  end;
  spfa;
  maxflow;
  close(input);
  close(output);
end.