QBBUILD - Xây dựng đường

Tác giả: ladpro98

Ngôn ngữ: Pascal

program qbbuild;
uses    math;
const   oo=high(longint);
        fi='';
        maxn=105;
var     n,m,res:longint;
        d:array[1..maxn,1..maxn] of longint;
        s:array[1..4] of longint;

procedure input;
var     inp:text;
        i,j,x,y,w:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        readln(inp,s[1],s[2],s[3],s[4]);
        for i:=1 to n do
        for j:=1 to n do
        begin
                if i=j then d[i,j]:=0
                else    d[i,j]:=oo;
        end;
        while not eof(inp) do
        begin
                readln(inp,x,y,w);
                if d[x,y]>w then
                begin
                        d[x,y]:=w;
                        d[y,x]:=w;
                end;
        end;
        close(inp);
end;

procedure floyd;
var     i,j,k:longint;
begin
        for k:=1 to n do
        for i:=1 to n do
        if d[i,k]<oo then
        for j:=1 to n do
        if d[k,j]<oo then
        begin
                if d[i,j]>d[i,k]+d[k,j] then
                        d[i,j]:=d[i,k]+d[k,j];
        end;
end;

procedure output;
var     I,J,p,q,r,T,sum:longint;
begin
        res:=oo;
        for i:=1 to n do
        for j:=i to n do
        begin
                for p:=1 to 4 do
                for q:=1 to 4 do
                for r:=1 to 4 do
                for t:=1 to 4 do
                if (p*q*r*t=24) and (p+q+r+t=10) then
                res:=min(res,d[i,s[p]]+d[i,s[q]]+d[j,s[r]]+d[j,s[t]]+d[i,j]);
        end;
        write(res);
end;

begin
        input;
        floyd;
        output;
end.

Download