FLOYD - Floyd hoặc Dijkstra ( Cơ bản )
Tác giả: ll931110
Ngôn ngữ: Pascal
Program FLOYD;
Const
input = '';
output = '';
Var
F,Trace: array[1..100,1..100] of longint;
n,m,k: longint;
val: array[1..100] of longint;
fi,fo: text;
Procedure LoadGraph;
Var
i,j,u,v: longint;
Begin
Assign(fi, input);
Reset(fi);
Readln(fi, n, m, k);
For i:= 1 to n do
For j:= 1 to n do if i = j then F[i,j]:= 0
else F[i,j]:= 10000000;
For i:= 1 to m do
Begin
Readln(fi, u,v,F[u,v]);
F[v,u]:= F[u,v];
End;
End;
Procedure Floyd;
Var
k,u,v: longint;
Begin
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 F[u,v] > F[u,k] + F[k,v] then
Begin
F[u,v]:= F[u,k] + F[k,v];
Trace[u,v]:= Trace[u,k];
End;
End;
Procedure PrintResult;
Var
x,u,v,i,j,num: longint;
Begin
Assign(fo, output);
Rewrite(fo);
For i:= 1 to k do
Begin
Readln(fi, x, u, v);
If x = 0 then writeln(fo, F[u,v]);
If x = 1 then
Begin
num:= 0;
Repeat
inc(num);
val[num]:= u;
u:= Trace[u, v];
Until u = v;
inc(num);
Write(fo, num, ' ');
For j:= 1 to num - 1 do write(fo, val[j], ' ');
Writeln(fo, v);
End;
End;
Close(fo);
Close(fi);
End;
Begin
LoadGraph;
Floyd;
PrintResult;
End.