LEM3 – spoj

Đề bài:

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 <bits/stdc++.h>
#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<<n)-1;
    fore(x,1,xx)
    {
        int l = 0;
        fore(i,1,n)
        if (get(x,i)) t[++l] = i;
        if (l == 1) continue;
        fore(i,1,l)
        {
            int x1 = off(x,t[i]);
            f[x][t[i]] = base;
            fore(j,1,l)
            if (i != j && f[x][t[i]] > 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<<t[i]<<' '<<f[x][t[i]]<<endl;
        }
    }
    ans = base;
    //cout<<get(36,1)<<endl;
    fore(i,1,n)
    ans = min(ans , f[xx][i]);
    cout<<ans;
    return 0;
}
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Comments

  1. Ban co the dua slove bang C++ dc khong , t k hieu pascal !

Speak Your Mind

*