ac1174.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1174;
const
  maxn=100;
  maxm=maxn*(maxn-1);
  paths=2;
  inf=999999999;
var
  v1,v2:array[1..maxm]of byte;
  cost:array[1..maxm]of word;
  flow:array[1..maxm]of byte;
  dist:array[1..maxn]of longint;
  edge:array[1..maxn]of integer;
  n,m,i,x,ans,p,t:longint;
  ok,more:boolean;
procedure aug;
  begin
    dist[1]:=0;for i:=2 to n do dist[i]:=inf;
    repeat
      more:=false;
      for i:=1 to m do
        if flow[i]=0 then begin
          t:=dist[v1[i]]+cost[i];
          if t<dist[v2[i]] then begin
            dist[v2[i]]:=t;edge[v2[i]]:=i;more:=true;
          end;
        end
        else begin
          t:=dist[v2[i]]-cost[i];
          if t<dist[v1[i]] then begin
            dist[v1[i]]:=t;edge[v1[i]]:=-i;more:=true;
          end;
        end;
    until not more;
    if dist[n]=inf then begin ok:=false;exit;end;
    x:=n;
    repeat
      if edge[x]>0 then begin
        t:=edge[x];
        inc(flow[t]);inc(ans,cost[t]);x:=v1[t];
      end
      else begin
        t:=-edge[x];
        dec(flow[t]);dec(ans,cost[t]);x:=v2[t];
      end;
    until x=1;
  end;
begin
  repeat
    read(n);if n=0 then halt;
    fillchar(cost,sizeof(cost),0);
    read(m);
    for i:=1 to m do begin
      read(v1[i*2],v2[i*2],cost[i*2]);
      v1[i*2-1]:=v2[i*2];v2[i*2-1]:=v1[i*2];cost[i*2-1]:=cost[i*2];
    end;
    m:=m*2;

    fillchar(flow,sizeof(flow),0);
    ans:=0;ok:=true;
    for p:=1 to paths do begin
      aug;
      if not ok then break;
    end;
    if ok then writeln(ans) else writeln('Back to jail');
  until false;
end.