LEM3 – spoj

Đề bài:

• http://vn.spoj.com/problems/LEM3/

Thuật toán:

• Đây là bài cơ bản của thuật toán quy hoạch động trạng thái.
• Nếu giải bài này bằng duyệt sẽ không ăn được hết test.
• Gọi F[i,state] là độ dài hành trình ngắn nhất khi đến được i và trạng thái thăm/chưa thăm các thành phố là state
  • state có dạng dãy bit 0,1. 1 là đã thăm, 0 là chưa thăm

Code:

Pascal (ideone)

uses    math;
const   fi='';
        fo='';
        maxn = 16;
        oo = 1 shl 16 -1;
var     f       :array[0..oo,1..maxn] of longint;
        i,j,n   :longint;
        c       :array[1..maxn,1..maxn] of longint;
        res     :longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);
        for i:=1 to n do
                for j:=1 to n do read(c[i,j]);
        close(input);
end;
function getbit( i,x :longint):byte;
begin
        getbit := (x shr (i-1)) and 1;
end;
function turnoff( i,x   :longint):longint;
begin
        turnoff := x and not (1 shl (i-1));
end;
procedure process;
var     i,j,k,t,state   :longint;
begin
        t := 1 shl n -1;
        for i:= 0 to t do
                for j:=1 to n do
                        f[i,j] := trunc(1e9);
        for i := 0 to t do
                for j := 1 to n do
                        if getbit(j,i)=1 then
                        begin
                                state := turnoff(j,i);
                                if state = 0 then begin f[i,j] := 0; break; end;
                                for k:=1 to n do
                                        if getbit(k,i)=1 then
                                                f[i,j] := min(f[i,j], f[state,k] + c[k,j]);
                        end;
        res := trunc(1e9);
        for i:=1 to n do
                res := min(res, f[t,i]);
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

C++ (ideone)

#include 
#define fore(i, a, b) for (int i = a; i <= b; i++)
#define ford(i, a, b) for (int i = a; i >= b; i--)
const int maxn = 1e5 ;
const int base = 1e9 + 7;
const int maxa = 1e6 * 5 + 1;
const int N = 50;
using namespace std;
int n,a[N][N],f[maxn][N],t[N],ans;

int get(int x,int i)
{
    return (x>>(i-1))&1;
}

int off(int x,int i)
{
    return x ^ (1<<(i-1));
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    //freopen("trip.INP","r",stdin);
    //freopen("trip.OUT","w",stdout);
    cin>>n;
    fore(i,1,n)
    fore(j,1,n) cin>>a[i][j];
    int xx = (1< f[x1][t[j]] + a[t[j]][t[i]])
                f[x][t[i]] = f[x1][t[j]] + a[t[j]][t[i]];
            //if (x == 36)
                //cout<