Hướng dẫn giải của TRIP

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const maxn=15;
      fi='';
      fo='';
      maxc=66000;
var n,re:longint;
    a:array[0..maxn,0..maxn] of longint;
    f:array[0..maxc,0..maxn] of longint;
    p:array[0..maxn] of longint;

procedure rf;
var i,j:byte;
begin
     assign(input,fi);
     reset(input);
     readln(n);
     dec(n);
     for i:=0 to n do
     begin
          for j:=0 to n do
              read(a[i,j]);
          readln;
     end;
     close(input);
end;

procedure init;
var i:byte;
begin
     p[0]:=1;
     for i:=1 to n+1 do p[i]:=p[i-1]*2;
end;

function out(j,s:longint):boolean;
begin
     s:=(s shr j) and 1;
     out:=(s=0);
end;

function min(a,b:longint):longint;
begin
     if a<b then min:=a else min:=b;
end;

procedure pr;
var i,j,s,t,max:longint;
begin
     init;
     max:=p[n+1]-1;
     for i:=0 to max do
         for j:=0 to n do
             f[i,j]:=1000000;
     for i:=0 to n do
         f[p[i],i]:=0;
     for s:=1 to max do
         for i:=0 to n do
             if not out(i,s) then
                for j:=0 to n do
                    if out(j,s) then
                    begin
                         t:=s or p[j];
                         f[t,j]:=min(f[t,j],f[s,i]+a[i,j]);
                    end;
     re:=1000000;
     for i:=0 to n do
         if f[max,i]<re then re:=f[max,i];
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include <cstdio>

#define INF 1000000000

int f[80000][20], a[20][20], n;

int min( int a, int b ) {
    return a < b ? a : b; 
}

int F( int mask, int end ) {
    if ( mask == 0 ) return 0;
    int & res = f[mask][end];
    if ( res == 0 ) {
        res = INF;
        for( int i = 0; i < n; ++i )
            if ( mask & ( 1 << i ) )
                res = min( res, F(mask & ~( 1 << i ), i) + a[i][end] );
    }
    return res;
}

int main() {
    scanf( "%d", &n );
    for( int i = 0; i < n; ++i )
        for( int j = 0; j < n; ++j ) scanf( "%d", &a[i][j] );
    int res = INF;
    for( int i = 0; i < n; ++i )
        res = min(res, F((1<<n)-1, i));
    printf( "%d\n", res );
    return 0;
}

Code mẫu của ladpro98

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.

Code mẫu của RR

{$R-,Q-}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=15;
  oo=1000000;
var
  t,n:longint;
  c:array[1..MAXN,1..MAXN] of longint;
  d:array[1..32767,1..15] of longint;
procedure inp; inline;
var
  f:text;
  i,j:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n);
  for i:=1 to n do
  for j:=1 to n do
    read(f,c[i,j]);
  t:=1 shl n-1;
  close(f);
end;
procedure ans; inline;
var
  f:text;
  kq,i:longint;
begin
  assign(f,FOUT); rewrite(f);
  kq:=oo;
  for i:=1 to n do
    kq:=min(kq,d[t,i]);
  writeln(f,kq);
  close(f);
end;
procedure solve; inline;
var
  i,j,ii,jj:longint;
begin
  for i:=1 to t do
  for j:=1 to n do
    d[i,j]:=oo;
  for i:=1 to n do
    d[1 shl (i-1),i]:=0;
  for i:=1 to t do
  for j:=1 to n do
  if (i shr (j-1)) and 1=1 then
    begin
      ii:=i and (not (1 shl (j-1)));
      for jj:=1 to n do
        if (ii shr (jj-1)) and 1=1 then
          d[i,j]:=min(d[i,j],d[ii,jj]+c[jj,j]);
    end;
end;
begin
  inp;
  solve;
  ans;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
int f[70000][17];
int main()
{
   // freopen("LEM3.in","r",stdin);
    int n, a[17][17],b[17],chay=1;
    scanf("%d",&n);
    for(int i = 0;i<n;i++)
        for(int j = 0;j<n;j++)
            scanf("%d",&a[i][j]);
    for(int i = 0;i<n;i++)
        f[0][i] = 0;
    b[0] = 1;
    for(int i = 1;i<n;i++)
    {
        b[i] = b[i-1]*2;
        chay = chay + b[i];
    }
    for(int i = 1;i<=chay;i++)
    {
        int t[n],m= i;
        for(int j = 0;j<n;j++)
        {
            t[j] = m%2;
            m = m/2;
        }
        for(int j = 0;j<n;j++)
        {
            if(t[j]==0)
                f[i][j]=0;
            else
            {
                int min = 1000000;
                for(int k = 0;k<n;k++)
                     if(f[i-b[j]][k]+a[k][j] < min && t[k]!=0 && k!=j)
                          min = f[i-b[j]][k]+a[k][j];
                if(min == 1000000) f[i][j] = 0;
                else f[i][j] = min;
            }
        }
    }
    int Min = 1000000;
    for(int i = 0;i<n;i++)
         if(f[chay][i]<Min)
             Min =f[chay][i];
    printf("%d",Min);
   // getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program LEM3;
        Const
                input  = '';
                output = '';
                   max = 32767;
        Var
                  d: array[0..16] of integer;
                  a: array[1..16,1..16] of integer;
                  F: array[0..max,1..16] of integer;
                  n: integer;

Procedure init;
          Var
                 fi: text;
                i,j: integer;
          Begin
                Assign(fi, input);
                        Reset(fi);

                Readln(fi, n);
                For i:= 1 to n do
                  For j:= 1 to n do read(fi, a[i,j]);

                Close(fi);
          End;

Procedure power;
          Var
                i: integer;
          Begin
                d[0]:= 1;
                For i:= 1 to n do d[i]:= d[i - 1] shl 1;
          End;

Procedure optimize;
          Var
                i,j,k,t,tmp: integer;
          Begin
                For i:= 0 to d[n] - 1 do
                  For j:= 1 to n do F[i,j]:= 1000000000;

                Fillchar(F[0], sizeof(F[0]), 0);
                For i:= 1 to n do F[d[i - 1],i]:= 0;

                For i:= 0 to d[n] - 1 do
                  For j:= 1 to n do if i and d[j - 1] = d[j - 1] then
                    Begin
                        t:= i - d[j - 1];
                        For k:= 1 to n do
                          if t and d[k - 1] = d[k - 1] then
                                Begin
                                        tmp:= F[t,k] + a[k,j];
                                        IF F[i,j] > tmp then F[i,j]:= tmp;
                                End;
                    End;
          End;

Procedure printresult;
          Var
                   fo: text;
                i,val: integer;
          Begin
                Assign(fo, output);
                        Rewrite(fo);

                val:= F[d[n] - 1,1];
                For i:= 2 to n do if val > F[d[n] - 1,i]
                                then val:= F[d[n] - 1,i];

                Writeln(fo, val);
                Close(fo);
          End;

Begin
        init;
        power;
        optimize;
        printresult;
End.

Code mẫu của skyvn97

#include<stdio.h>
#define INF   1e9
#define MAX   22
int c[MAX][MAX];
int f[MAX][100100];
int n;
void init(void) {
    int i,j;
    scanf("%d",&n);
    for (i=1;i<=n;i=i+1)
        for (j=1;j<=n;j=j+1)
            scanf("%d",&c[i][j]);
    for (i=1;i<=n;i=i+1)
        for (j=0;j<(1<<n);j=j+1)
            f[i][j]=INF;
}
int r(int i,int s) {
    if ((s|(1<<(i-1)))!=s) return (INF);
    if (s==(1<<(i-1))) return (0);
    if (f[i][s]<INF) return (f[i][s]);
    int j,t;
    for (j=1;j<=n;j=j+1)
        if ((i!=j) && ((s|(1<<(j-1)))==s)) {
            t=r(j,s&((1<<n)-1-(1<<(i-1))))+c[j][i];
            if (f[i][s]>t) f[i][s]=t;
        }
    return (f[i][s]);
}
void process(void) {
    int m=INF;
    int i;
    for (i=1;i<=n;i=i+1)
        if (m>r(i,(1<<n)-1)) m=r(i,(1<<n)-1);
    printf("%d",m);
}
int main(void) {
    init();
    process();
}

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int n, c[20][20], f[1<<17][20];

int main() {
    cin >> n;
    for(int i=0;i<n;++i) for(int j=0;j<n;++j) cin >> c[i][j];
    memset( f, 0x1f, sizeof(f));
    for(int i=0;i<n;++i) f[1<<i][i] = 0;
    for(int b=1;b<(1<<n);++b)
        for(int i=0;i<n;++i) 
            for(int j=0;j<n;++j) if((b&(1<<j))==0)
                f[b|(1<<j)][j] <?= f[b][i] + c[i][j];
    cout << *min_element(f[(1<<n)-1], f[(1<<n)-1]+n) << endl;
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • -1
    i_loveMA  đã bình luận lúc 29, Tháng 12, 2024, 1:55

    include <bits/stdc++.h>

    using namespace std;

    define ll long long

    define sz(x) ((int)x.size())

    define st first

    define nd second

    define all(a) a.begin(), a.end()

    define FOR(i, a, b) for (int i = (a); i <= (b); ++i)

    define FOD(i, a, b) for (int i = (a); i >= (b); --i)

    typedef pair<int,int> ii; typedef pair<ll, ll> pll; const int mod = 1e9 + 7; const int base = 5e6 - 1; const int maxn = 5e5 + 2; const int maxm = 1e4 + 2; void maximize(ll &a, ll b) { a = max(a, b); } void minimize(ll &a, ll b) { a = min(a, b); } int n; ll ans = 1e18, t = 0, cnt = 0; int c[16][16]; bitset<16> used; void dfs(int u) { if (t > ans) return; used[u] = 1; ++cnt; if (cnt == n) { ans = min(ans, t); } for (int i = 1; i <= n; ++i) { if (i != u && used[i] == 0) { t += c[u][i]; dfs(i); t -= c[u][i]; } } used[u] = 0; --cnt; }

    define task "test"

    int32t main() { iosbase::syncwithstdio(false); cin.tie(0); if(fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } cin >> n; FOR(i, 1, n) FOR(j, 1, n) { cin >> c[i][j]; } for (int i = 1; i <= n; ++i )dfs(i); cout << ans; } /* ---INPUT--- 6 0 1 2 1 3 4 5 0 3 2 3 4 4 1 0 2 1 2 4 2 5 0 4 3 2 5 3 5 0 2 5 4 3 3 1 0 ---OUTPUT--- 8 */


  • 0
    ym_yendong_vucongdat  đã bình luận lúc 6, Tháng 11, 2024, 13:05

    cảm ơn mại người đã chỉ ạ!