记录编号	39144	评测结果	AAAAAAAAAA
题目名称	841.塔防游戏	最终得分	100
用户昵称	fuhao	是否通过	通过
代码语言	Pascal	运行时间	0.669 s
提交时间	2012-07-05 14:35:33	内存使用	17.40 MiB

const maxn=1001; maxm=500000;
var
 dis1,dis,dis2,hnum,h:array[0..maxn] of longint;
 w,a,c:array[0..maxn,0..maxn] of longint;
 f:array[0..maxm,1..3] of longint;
 u:array[0..maxn] of boolean;
 s,t,ans,i,max,n,m:longint; found:boolean;
 procedure insert(x,y:longint);
 begin inc(a[x,0]); a[x,a[x,0]]:=y; c[x,y]:=1;
       inc(a[y,0]); a[y,a[y,0]]:=x;
 end;
 procedure sap(k:longint);
 var i,temp,hmin:longint;
 begin
  temp:=max; hmin:=n-1;
  if k=t then
   begin
    found:=true;
    ans:=ans+max;
    exit;
   end;
  for i:=1 to a[k,0] do
   if c[k,a[k,i]]>0 then
    begin
     if h[a[k,i]]+1=h[k] then
      begin
       if max>c[k,a[k,i]] then max:=c[k,a[k,i]];
       sap(a[k,i]);
       if h[s]>=n then exit;
       if found then break;
       max:=temp;
      end;
     if hmin>h[a[k,i]] then hmin:=h[a[k,i]];
    end;
  if found then
   begin
    dec(c[k,a[k,i]],max);
    inc(c[a[k,i],k],max);
   end else
   begin
    dec(hnum[h[k]]);
    if hnum[h[k]]=0 then h[s]:=n;
    h[k]:=hmin+1;
    inc(hnum[h[k]]);
   end;
 end;
 procedure dijkstra(ss:longint);
 var i,j,k:longint;
 begin
  fillchar(u,sizeof(u),#0);
  fillchar(dis,sizeof(dis),$7f div 2);
  dis[ss]:=0;
  for i:=1 to n do
   begin
    k:=0;
    for j:=1 to n do
     if (not u[j]) and (dis[j]<dis[k]) then k:=j;
    if k=0 then break;
    u[k]:=true;
    for j:=1 to n do
     if dis[j]>dis[k]+w[k,j] then
      dis[j]:=dis[k]+w[k,j];
   end;
 end;
begin
 assign(input,'defence.in'); reset(input);
 assign(output,'defence.out'); rewrite(output);
 readln(n,m,s,t);
 fillchar(w,sizeof(w),$7f div 2);
 for i:=1 to m do
  begin
   readln(f[i,1],f[i,2],f[i,3]);
   if w[f[i,1],f[i,2]]>f[i,3] then
    w[f[i,1],f[i,2]]:=f[i,3];
   if w[f[i,2],f[i,1]]>f[i,3] then
    w[f[i,2],f[i,1]]:=f[i,3];
  end;
 dijkstra(s); dis1:=dis;
 dijkstra(t); dis2:=dis;
 fillchar(a,sizeof(a),0);
 for i:=1 to m do
  if dis1[f[i,1]]+f[i,3]+dis2[f[i,2]]=dis1[t] then
   insert(f[i,1],f[i,2]) else
  if dis1[f[i,2]]+f[i,3]+dis2[f[i,1]]=dis1[t] then
   insert(f[i,2],f[i,1]);
 hnum[0]:=n; h[s]:=0;
 while h[s]<n do
  begin
   found:=false;
   max:=maxlongint;
   sap(s);
  end;
 writeln(ans);
 close(input); close(output);
end.