FLOYD - Floyd hoặc Dijkstra ( Cơ bản )
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+}
uses math;
const
FINP = '';
FOUT = '';
MAXN = 111;
var
f1,f2 : text;
n,m,k : longint;
c,trace : array[1..MAXN,1..MAXN] of longint;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1);
close(f2);
end;
procedure inp;
var
i,u,v:longint;
begin
read(f1,n,m,k);
for u:=1 to n do
for v:=1 to n do
c[u,v]:=1000111000;
for i:=1 to m do
begin
read(f1,u,v,c[u,v]);
c[v,u]:=c[u,v];
end;
for i:=1 to n do c[i,i]:=0;
end;
procedure init;
var
i,j,k:longint;
begin
for i:=1 to n do
for j:=1 to n do
trace[i,j]:=j;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if c[i,j]>c[i,k]+c[k,j] then
begin
c[i,j]:=c[i,k]+c[k,j];
trace[i,j]:=trace[i,k];
end;
end;
procedure solve;
var
i,q,u,v,count:longint;
begin
for i:=1 to k do
begin
read(f1,q,u,v);
if q=0 then writeln(f2,c[u,v])
else
begin
count:=1; q:=u;
repeat
inc(count);
u:=trace[u,v];
until u=v;
write(f2,count,' ',q);
u:=q;
repeat
u:=trace[u,v];
write(f2,' ',u);
until u=v;
writeln(f2);
end;
end;
end;
begin
openF;
inp;
init;
solve;
closeF;
end.