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 fi='';
      fo='';
      max=5050;
      maxc=1000000000;
      f:array[0..7] of longint=(1,1,2,6,24,120,720,5040);
type ar=array[1..7] of longint;
var a:array[1..7,1..7] of longint;
    d:array[1..max] of longint;
    dau,c:array[1..max] of byte;
    b,y:ar;
    n,x,t,min,i,j,m:longint;

function conv(var b:ar):longint;
var t,r,i,j:longint;
begin
     r:=1;
     fillchar(c,sizeof(c),0);
     for i:=1 to m do
     begin
          t:=-1;
          for j:=1 to b[i] do
              if c[j]=0 then inc(t);
          r:=r+t*f[m-i];
          c[b[i]]:=1;
     end;
     conv:=r;
end;

procedure reconv(var b:ar;x:longint);
var t,i,j:longint;
begin
     dec(x);
     fillchar(c,sizeof(c),0);
     for i:=1 to m-1 do
     begin
          t:=x div f[m-i]+1;
          x:=x mod f[m-i];
          j:=0;
          while t>0 do
          begin
               inc(j);
               if c[j]=0 then dec(t);
          end;
          b[i]:=j;
          c[j]:=1;
     end;
     for i:=1 to m do
         if c[i]=0 then
         begin
              b[m]:=i;
              break;
         end;
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     m:=0;
     while not eoln do
     begin
          inc(m);
          read(b[m]);
     end;
     x:=conv(b);
     for i:=1 to m do
         for j:=1 to m do
             read(a[i,j]);
     n:=f[m];
     for i:=1 to n do d[i]:=maxc;
     d[x]:=0; dau[x]:=1;
     repeat
           reconv(b,x);
           for i:=1 to m-1 do
               for j:=i+1 to m do
               begin
                    y:=b;
                    y[i]:=b[j]; y[j]:=b[i];
                    t:=conv(y);
                    if (dau[t]=0) and (d[x]+a[i,j]<d[t]) then
                       d[t]:=d[x]+a[i,j];
               end;
           min:=maxc-1;
           for i:=1 to n do
               if (dau[i]=0) and (d[i]<min) then
               begin
                    min:=d[i];
                    t:=i;
               end;
           x:=t; dau[t]:=1;
     until dau[1]>0;
     writeln(d[1]);
     close(input); close(output);
end.

Code mẫu của ladpro98

{$MODE OBJFPC}
program v8sort;
uses    math;
type    e=record
        v,p:longint;
        end;
const   maxn=10;
        maxl=5555;
        oo=trunc(1e9);
        fi='';
var     c:array[1..maxn,1..maxn] of longint;
        a,s,f:array[0..maxn] of longint;
        check:array[1..maxn] of boolean;
        d,h,pos:array[0..maxl] of longint;
        b:array[1..maxn] of e;
        n,dd,nh:longint;

procedure input;
var     inp:text;
        i,j:longint;
begin
        assign(inp,fi);
        reset(inp);
        while not seekeoln(inp) do
        begin
                inc(n);
                read(inp,b[n].v);
                b[n].p:=n;
        end;
        for i:=1 to n do
        begin
                for j:=1 to n do
                read(inp,c[i,j]);
                readln(inp);
        end;
        close(inp);
end;

procedure init;
var     i,j:longint;
        t:e;
begin
        f[1]:=1;
        for i:=2 to n do f[i]:=i*f[i-1];
        for i:=1 to n do
        for j:=i+1 to n do
        if b[i].v>b[j].v then
        begin
                t:=b[i];
                b[i]:=b[j];
                b[j]:=t;
        end;
        dd:=1;
        for i:=1 to n do
        begin
                s[b[i].p]:=dd;
                inc(dd);
        end;
        for i:=1 to f[n] do d[i]:=oo;
end;

function toNum:longint;
var     i,j,t,sum:longint;
begin
        for i:=1 to n do check[i]:=false;
        sum:=0;
        for i:=1 to n do
        begin
                t:=0;
                for j:=1 to a[i]-1 do
                if not check[j] then inc(t);
                inc(sum,t*f[n-i]);
                check[a[i]]:=true;
        end;
        exit(sum+1);
end;

procedure toMask(p:longint);
var     i,j,t,k:longint;
begin
        for i:=1 to n do check[i]:=false;
        for i:=1 to n do
        begin
                for j:=n-1 downto 0 do
                begin
                        t:=0;
                        for k:=1 to j do
                        if not check[k] then inc(t);
                        if (not check[j+1]) and (t*f[n-i]<p) then break;
                end;
                s[i]:=j+1;
                check[j+1]:=true;
                dec(p,t*f[n-i]);
        end;
end;

procedure update(v:longint);
var     p,c:longint;
begin
        c:=pos[v];
        if c=0 then begin
                inc(nh);
                c:=nh;
        end;
        repeat
                p:=c shr 1;
                if (p=0) or (d[h[p]]<=d[v]) then break;
                h[c]:=h[p];
                pos[h[c]]:=c;
                c:=p;
        until false;
        h[c]:=v;
        pos[v]:=c;
end;

function extract:longint;
var     v,p,c:longint;
begin
        result:=h[1];
        v:=h[nh];
        dec(nh);
        p:=1;
        repeat
                c:=p shl 1;
                if (c<nh) and (d[h[c+1]]<d[h[c]]) then inc(c);
                if (c>nh) or (d[h[c]]>=d[v]) then break;
                h[p]:=h[c];
                pos[h[p]]:=p;
                p:=c;
        until false;
        h[p]:=v;
        pos[v]:=p;
end;

procedure dijkstra;
var     i,j,u,t,v:longint;
begin
        a:=s;
        d[toNum]:=0;
        update(toNum);
        repeat
                u:=extract;
                toMask(u);
                for i:=1 to n-1 do
                for j:=i+1 to n do
                begin
                        a:=s;
                        t:=a[i];
                        a[i]:=a[j];
                        a[j]:=t;
                        v:=toNum;
                        if d[v]>d[u]+c[i,j] then begin
                                d[v]:=d[u]+c[i,j];
                                update(v);
                        end;
                end;
        until nh=0;
end;

procedure output;
var     i:longint;
begin
        for i:=1 to n do a[i]:=i;
        write(d[toNum]);
end;

begin
        input;
        init;
        Dijkstra;
        output;
end.

Code mẫu của RR

{$R+,Q+}
const
  FINP='';
  FOUT='';
  MAXN=7;
  MAX=5040;
  oo=1000000000;
type
  arr=array[1..MAXN] of longint;
var
  hsize,sl,n:longint;
  c:array[1..MAXN,1..MAXN] of longint;
  hv:array[1..MAX] of arr;
  hpos,h,d:array[1..MAX] of longint;
  xet:array[1..MAXN] of longint;
  kq,a:arr;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure inp;
var
  f:text;
  i,j:longint;
begin
  assign(f,FINP); reset(f);
  n:=0;
  while not eoln(f) do
    begin
      inc(n);
      read(f,a[n]);
    end;
  for i:=1 to n do
  for j:=1 to n do
    read(f,c[i,j]);
  close(f);
end;
procedure ans;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,d[1]);
  close(f);
end;
procedure luu;
begin
  inc(sl); hv[sl]:=kq;
end;
procedure try(i:longint);
var
  j:longint;
begin
  for j:=1 to n do
  if xet[j]=0 then
    begin
      xet[j]:=1; kq[i]:=j;
      if i<n then try(i+1)
      else luu;
      xet[j]:=0;
    end;
end;
operator <(a,b:arr) c:boolean;
var
  i:longint;
begin
  for i:=1 to n do
    if a[i]<b[i] then exit(true)
    else if a[i]>b[i] then exit(false);
  exit(false);
end;
operator =(a,b:arr) c:boolean;
var
  i:longint;
begin
  for i:=1 to n do
    if a[i]<>b[i] then exit(false);
  exit(true);
end;
function find(a:arr):longint;
var
  l,r,mid:longint;
begin
  l:=1; r:=sl;
  repeat
    mid:=(l+r) div 2;
    if hv[mid]<a then l:=mid
    else r:=mid;
  until r-1<=l;
  if a=hv[l] then exit(l)
  else exit(r);
end;
procedure downHeap(i:longint);
var
  j:longint;
begin
  j:=i shl 1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (d[h[j+1]]<d[h[j]]) then inc(j);
      if d[h[j]]<d[h[i]] then
        begin
          swap(hpos[h[i]],hpos[h[j]]);
          swap(h[i],h[j]);
        end;
      i:=j; j:=i shl 1;
    end;
end;
procedure upHeap(i:longint);
var
  j:longint;
begin
  j:=i shr 1;
  while (i>1) and (d[h[i]]<d[h[j]]) do
    begin
      swap(hpos[h[i]],hpos[h[j]]);
      swap(h[i],h[j]);
      i:=j; j:=i shr 1;
    end;
end;
procedure push(u:longint);
begin
  inc(hsize); h[hsize]:=u; hpos[u]:=hsize;
  upHeap(hsize);
end;
procedure pop(var u:longint);
begin
  u:=h[1]; hpos[u]:=0;
  swap(h[1],h[hsize]);
  hpos[h[1]]:=1;
  dec(hsize);
  downHeap(1);
end;
procedure init;
var
  u,i:longint;
begin
  sl:=0;
  try(1);
  for i:=1 to sl do d[i]:=oo;
  u:=find(a); d[u]:=0;
  h[1]:=u; hpos[u]:=1; hsize:=1;
end;
procedure solve;
var
  u,v,i,j:longint;
  x,y:arr;
begin
  while hsize>0 do
    begin
      pop(u);
      if u=1 then exit;
      x:=hv[u];
      for i:=1 to n-1 do
      for j:=i+1 to n do
        begin
          y:=x;
          swap(y[i],y[j]);
          v:=find(y);
          if d[u]+c[i,j]<d[v] then
            begin
              d[v]:=d[u]+c[i,j];
              if hpos[v]=0 then push(v)
              else upHeap(hpos[v]);
            end;
        end;
    end;
end;
begin
  inp;
  init;
  solve;
  ans;
end.

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(typeof(n) i = 0; i < (n); ++i)
#define Repd(i,n) for(typeof(n) i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(typeof(b) i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(typeof(a) i = (a); i >= (b); --i)
#define Fit(i,v) for(typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
#define nl puts("")
#define sp printf(" ")
#define ok puts("ok")
//#include <conio.h>

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} };
template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

const double PI = 2 * acos(0);
const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dr[] = {0, +1, 0, -1};
const int dc[] = {+1, 0, -1, 0};
const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const double eps = 1e-9;
const ll mod = 100000007;
typedef pair<int, int> II;

#define maxn 505
#define maxe 1000005

int n, a[10][10], x;
int f[maxe], mu7[10];
priority_queue< II > que;
char s[maxn];
vector<int> st, fn;

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    gets(s);
    istringstream iss(s);
    while(iss >> x){
        st.pb(x);
        fn.pb(x);
    }
    n = sz(st);
    sort(all(fn));
    Rep(i, n) Rep(j, n) scanf("%d", &a[i][j]);
    mu7[0] = 1;
    For(i, 1, 7) mu7[i] = 7 * mu7[i - 1];
    int dau = 0, cuoi = 0;
    Rep(i, n) Rep(j, n){
        if(st[j] < st[i]) dau += mu7[i];
        if(fn[j] < fn[i]) cuoi += mu7[i];
    }
    ms(f, 0x3f);
    f[dau] = 0;
    que.push(mp(0, dau));
    int u, v, t;

    while(!que.empty()){
        u = que.top().se; v = -que.top().fi; que.pop();
        if(u == cuoi) break;
        if(f[u] < v) continue;
        vector<int> temp(n); t = u;
        Rep(i, n){
            temp[i] = t % 7;
            t /= 7;
        }
        Rep(i, n) For(j, i + 1, n - 1){
            t = u + (temp[j] - temp[i]) * mu7[i] + (temp[i] - temp[j]) * mu7[j];
            if(f[t] > f[u] + a[i][j]){
                f[t] = f[u] + a[i][j];
                que.push(mp(-f[t], t));
            }
        }

    }
    cout << f[cuoi];
}

Code mẫu của ll931110

{$MODE DELPHI}
Program V8SORT;
  Const
    input  = '';
    output = '';
    maxn = 7;
    maxc = 100000000;
    maxv = 2500000;
  Type
    arr = array[1..maxn] of integer;
  Var
    F: array[1..maxv] of integer;
    heap,pos: array[1..2500000] of integer;
    free: array[1..maxv] of boolean;
    c: array[1..maxn,1..maxn] of integer;
    n,nHeap: integer;
    a,k,p: arr;

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

    n:= 0;
    While not SeekEoln(fi) do
      Begin
        inc(n);
        Read(fi, a[n]);
      End;
    Readln(fi);

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

    Close(fi);
  End;

Procedure swap(var x,y: integer);
  Var
    t: integer;
  Begin
    t:= x;
    x:= y;
    y:= t;
  End;

Procedure update(v: integer);
  Var
    parent,child: integer;
  Begin
    child:= pos[v];
    If child = 0 then
      Begin
        inc(nHeap);
        child:= nHeap;
      End;

    parent:= child div 2;
    While (parent > 0) and (F[heap[parent]] > F[v]) do
      Begin
        heap[child]:= heap[parent];
        pos[heap[child]]:= child;

        child:= parent;
        parent:= child div 2;
      End;

    heap[child]:= v;
    pos[v]:= child;
  End;

Function pop: integer;
  Var
    r,c,v: integer;
  Begin
    pop:= heap[1];
    v:= heap[nHeap];
    dec(nHeap);

    r:= 1;
    While r * 2 <= nHeap do
      Begin
        c:= r * 2;
        If (c < nHeap) and (F[heap[c + 1]] < F[heap[c]]) then inc(c);

        If F[v] <= F[heap[c]] then break;

        heap[r]:= heap[c];
        pos[heap[r]]:= r;

        r:= c;
      End;

    heap[r]:= v;
    pos[v]:= r;
  End;

Function calc(d: arr): integer;
  Var
    i,tmp: integer;
  Begin
    tmp:= d[1];
    For i:= 2 to n do tmp:= tmp * (n + 1) + d[i];
    calc:= tmp;
  End;

Procedure solve;
  Var
    fo: text;
    i,j,u,s,tmp,res: integer;
  Begin
    Fillchar(free, sizeof(free), true);
    For i:= 1 to maxv do F[i]:= maxc;

    Fillchar(pos, sizeof(pos), 0);
    nHeap:= 0;

    For i:= 1 to n do p[i]:= i;

    res:= calc(p);
    F[res]:= 0;
    update(res);
    free[res]:= false;

    For i:= 1 to n - 1 do
      For j:= i + 1 to n do
        if a[i] > a[j] then
          Begin
            swap(a[i], a[j]);
            swap(p[i], p[j]);
          End;

    res:= calc(p);
    Repeat
      u:= pop;
      If u = res then break;

      tmp:= u;
      free[u]:= false;

      For i:= n downto 1 do
        Begin
          k[i]:= tmp mod (n + 1);
          tmp:= tmp div (n + 1);
        End;

      For i:= 1 to n do
        For j:= 1 to n do
          Begin
            swap(k[i], k[j]);
            s:= calc(k);

            If free[s] and
              (F[s] > F[u] + c[i,j]) then
                Begin
                  F[s]:= F[u] + c[i,j];
                  update(s);
                End;

            swap(k[i], k[j]);
          End;
    Until nHeap = 0;

    Assign(fo, output);
      Rewrite(fo);
      Writeln(fo, F[res]);
    Close(fo);
  End;

Begin
  init;
  solve;
End.

Code mẫu của skyvn97

#include<cstdio>
#include<iostream>
#include<map>
#include<queue>
#include<sstream>
#include<string>
#include<vector>
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define fi   first
#define se   second
using namespace std;
const int INF=(int)1e9+7;
typedef pair<int,vector<int> > State;
map<vector<int>,int> dis;
vector<int> sta;
int cost[11][11];
int n;
void init(void) {
    string inp;
    getline(cin,inp);
    stringstream ss(inp);
    int x;
    while (ss>>x) sta.push_back(x);
    n=sta.size();
    REP(i,n) REP(j,n) cin>>cost[i][j];
}
bool isEnd(const vector<int> &v) {
    REP(i,(int)v.size()-1) if (v[i]>v[i+1]) return (false);
    return (true);
}
int getDis(const vector<int> &v) {
    return (dis.find(v)==dis.end()?INF:dis[v]);
}
void dijkstra(void) {
    priority_queue<State,vector<State>,greater<State> > q;
    dis[sta]=0;
    q.push(State(0,sta));
    while (!q.empty()) {
        int d=q.top().fi;
        vector<int> cur=q.top().se;
        q.pop();
        if (d!=getDis(cur)) continue;
        if (isEnd(cur)) {
            printf("%d\n",d);
            return;
        }
        REP(i,n) REP(j,n) if (i<j) {
            swap(cur[i],cur[j]);
            if (getDis(cur)>d+cost[i][j]) {
                dis[cur]=d+cost[i][j];
                q.push(State(d+cost[i][j],cur));
            }
            swap(cur[i],cur[j]);
        }
    }
}
int main(void) {
    init();
    dijkstra();
    return 0;
}

Code mẫu của khuc_tuan

import java.util.*;

public class Main {

    static Map<int[], Integer> ma;

    public static void main(String[] args) {
        ma = new TreeMap<int[], Integer>(new Comparator<int[]>() {
            public int compare(int[] a,int[] b) {
                if(a.length!=b.length) return a.length-b.length;
                for(int i=0;i<a.length;++i) if(a[i]!=b[i]) return a[i]-b[i];
                return 0;
            }
        });
        int N=0;
        int[] a;
        int[][] c;
        Scanner sc = new Scanner(System.in);
        String ss = sc.nextLine();
        StringTokenizer st = new StringTokenizer(ss);
        while(st.hasMoreTokens()) {
            ++N;
            st.nextToken();
        }
        st = new StringTokenizer(ss);
        a = new int[N];
        c = new int[N][N];
        for(int i=0;i<N;++i) a[i] = Integer.parseInt(st.nextToken());
        for(int i=0;i<N;++i) for(int j=0;j<N;++j) c[i][j] = sc.nextInt();

        Queue<int[]> q = new LinkedList<int[]>();

        q.add(a);
        ma.put( a, 0);
        int result = 1000000000;

        while(!q.isEmpty()) {
            int[] u = q.remove();
            int step = ma.get(u);
            boolean ok = true;
            for(int i=0;i<u.length-1;++i) if(u[i]>u[i+1]) ok = false;
            if(ok) result = Math.min( result, step);
            for(int i=0;i<u.length;++i) for(int j=i+1;j<u.length;++j) {
                int[] v = u.clone();
                int tt = v[i]; v[i] = v[j]; v[j] = tt;
                if(ma.containsKey(v)) {
                    int oldStep = ma.get(v);
                    if(oldStep>step+c[i][j]) {
                        Integer I = step + c[i][j];
                        ma.put(v, I);
                        q.add(v);
                    }
                }
                else {
                    ma.put(v, step + c[i][j]);
                    q.add(v);
                }
            }
        }

        System.out.println(result);
    }
}