HIWAY - Hai đường đi

Tác giả: RR

Ngôn ngữ: Pascal

var
  cnt,res,k,u,v,n,m,s,t,ss:longint;
  fl,a,c,trace:array[1..111,1..111] of longint;
  kq:array[1..111] of longint;

procedure print(s:longint);
    var
      u:longint;
    begin
      inc(cnt); kq[cnt]:=s;
      if s=t then exit;
      for u:=1 to n do
        if fl[s,u]=1 then
          begin
            fl[s,u]:=0;
            print(u);
            exit;
          end;
    end;

begin
  read(n,m,s,t);

  for u:=1 to n do
  for v:=1 to n do
    begin
      a[u,v]:=1000111000;
      if u=v then a[u,v]:=0;
      trace[u,v]:=v;
    end;

  for m:=1 to m do
    begin
      read(u,v,a[u,v]);
      a[v,u]:=a[u,v];
    end;

  c:=a;
  for k:=1 to n do
    for u:=1 to n do
    for v:=1 to n do
      if c[u,v]>c[u,k]+c[k,v] then
        begin
          c[u,v]:=c[u,k]+c[k,v];
          trace[u,v]:=trace[u,k];
        end;
  res:=c[s,t];

  ss:=s;
  while ss<>t do
    begin
      fl[ss,trace[ss,t]]:=1;
      a [trace[ss,t],ss]:=-a[ss,trace[ss,t]];
      a [ss,trace[ss,t]]:=1000111000;
      ss:=trace[ss,t];
    end;

  c:=a;
  for u:=1 to n do
  for v:=1 to n do
    trace[u,v]:=v;

  for k:=1 to n do
    for u:=1 to n do
    for v:=1 to n do
      if c[u,v]>c[u,k]+c[k,v] then
        begin
          c[u,v]:=c[u,k]+c[k,v];
          trace[u,v]:=trace[u,k];
        end;
  res:=res+c[s,t];

  ss:=s;
  while ss<>t do
    begin
      if c[ss,trace[ss,t]]<0 then fl[trace[ss,t],ss]:=0
      else fl[ss,trace[ss,t]]:=1;
      ss:=trace[ss,t];
    end;

  writeln(res);
  print(s);
  write(cnt); for u:=1 to cnt do write(' ',kq[u]); writeln;
  cnt:=0;
  print(s);
  write(cnt); for u:=1 to cnt do write(' ',kq[u]); writeln;
end.

Download