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.