QBBUILD - Xây dựng đường
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
Program QBBUILD;
Const
input = '';
output = '';
maxn = 100;
maxc = 100000000;
maxd = 4;
Var
c: array[1..maxn,1..maxn] of integer;
a: array[1..maxd] of integer;
n,res: integer;
Procedure LoadGraph;
Var
f: text;
i,j,k,u,v: integer;
Begin
Assign(f, input);
Reset(f);
Readln(f, n);
For i:= 1 to n do
For j:= 1 to n do
if i = j then c[i,j]:= 0 else c[i,j]:= maxc;
Readln(f, a[1], a[2], a[3], a[4]);
While not Eof(f) do
Begin
Readln(f, u, v, k);
If c[u,v] > k then
Begin
c[u,v]:= k;
c[v,u]:= k;
End;
End;
Close(f);
End;
Procedure Floyd;
Var
u,v,k: integer;
Begin
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 c[u,v]:= c[u,k] + c[k,v];
End;
Procedure solve;
Var
f: text;
i,j,tmp: integer;
Begin
res:= maxc;
For i:= 1 to n do
For j:= 1 to n do
Begin
tmp:= c[i,a[1]] + c[i,a[2]] + c[j,a[3]] + c[j,a[4]];
If tmp > c[i,a[1]] + c[i,a[3]] + c[j,a[2]] + c[j,a[4]]
then tmp:= c[i,a[1]] + c[i,a[3]] + c[j,a[2]] + c[j,a[4]];
If tmp > c[i,a[1]] + c[i,a[4]] + c[j,a[2]] + c[j,a[3]]
then tmp:= c[i,a[1]] + c[i,a[4]] + c[j,a[2]] + c[j,a[3]];
tmp:= tmp + c[i,j];
If res > tmp then res:= tmp;
End;
Assign(f, output);
Rewrite(f);
Writeln(f, res);
Close(f);
End;
Begin
LoadGraph;
Floyd;
solve;
End.