LEM3 - TRIP

Tác giả: ladpro98

Ngôn ngữ: Pascal

program lem3;//dp;
uses    math;
const   fi='';
        oo=1000000;
        maxN=15;
var     c:array[1..maxN,1..maxN] of longint;
        f:array[1..maxN,0..(1 shl maxN)] of longint;
        pow:array[0..maxN] of longint;
        n:longint;

procedure input;
var     inp:text;
        i,j:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        for j:=1 to n do
        read(inp,c[i,j]);
        close(inp);
end;

function getbit(i,j:longint):longint;
begin
        exit(i shr (j-1) and 1);
end;

procedure init;
var     i:longint;
begin
        pow[0]:=1;
        for i:=1 to n do
        pow[i]:=pow[i-1] shl 1;
end;

procedure dp;
var     i,j,k:longint;
begin
        for j:=1 to pow[n]-1 do
        for i:=1 to n do
        begin
                f[i,j]:=oo;
                for k:=1 to n do
                if k<>i then
                if getbit(j,k)=1 then
                f[i,j]:=min(f[i,j],f[k,j-pow[k-1]]+c[k,i]);
        end;
end;

procedure output;
var     i,j,res:longint;
begin
        res:=oo;
        for i:=1 to n do
        res:=min(res,f[i,pow[n]-1-pow[i-1]]);
        write(res);
end;

begin
        input;
        init;
        dp;
        output;
end.

Download