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.

Download