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='';
      maxm=100100;
      maxn=1010;
      oo=1000000100;
var n,m,k,nh:longint;
    pos,sl,cur:array[1..maxn] of longint;
    a,v:array[1..maxm*2] of longint;
    b,c,e:array[1..maxm] of longint;
    f:array[0..10,1..maxn] of real;
    d:array[0..10,1..maxn] of boolean;
    p:array[0..10,1..maxn] of longint;
    h,g:array[1..11*maxn] of longint;
    pow:array[0..10] of longint;

procedure rf;
var i,j:longint;
begin
     read(n,m,k);
     for i:=1 to m do
     begin
          read(b[i],c[i],e[i]);
          inc(sl[b[i]]);
          inc(sl[c[i]]);
     end;
     pos[1]:=1; cur[1]:=1;
     for i:=2 to n+1 do
     begin
          pos[i]:=pos[i-1]+sl[i-1];
          cur[i]:=pos[i];
     end;
     for i:=1 to m do
     begin
          a[cur[b[i]]]:=c[i];
          v[cur[b[i]]]:=e[i];
          inc(cur[b[i]]);
          a[cur[c[i]]]:=b[i];
          v[cur[c[i]]]:=e[i];
          inc(cur[c[i]]);
     end;
end;

procedure init;
var i,j:longint;
begin
     pow[0]:=1;
     for i:=1 to k do pow[i]:=pow[i-1]*2;
     for i:=0 to k do
       for j:=1 to n do
         f[i,j]:=oo;
     nh:=0;
end;

procedure update(x,y:longint);
var cha,con:longint;
begin
     con:=p[x,y];
     if con=0 then
     begin
          nh:=nh+1;
          con:=nh;
     end;
     cha:=con shr 1;
     while (cha>0) and (f[g[cha],h[cha]]>f[x,y]) do
     begin
          h[con]:=h[cha];
          g[con]:=g[cha];
          p[g[con],h[con]]:=con;
          con:=cha;
          cha:=con shr 1;
     end;
     h[con]:=y; g[con]:=x;
     p[x,y]:=con;
end;

procedure pop(var xx,yy:longint);
var x,y,cha,con:longint;
begin
     xx:=g[1]; yy:=h[1];
     x:=g[nh]; y:=h[nh];
     nh:=nh-1;
     cha:=1; con:=2;
     while con<=nh do
     begin
          if (con<nh) and (f[g[con+1],h[con+1]]<f[g[con],h[con]]) then con:=con+1;
          if f[x,y]<=f[g[con],h[con]] then break;
          h[cha]:=h[con];
          g[cha]:=g[con];
          p[g[cha],h[cha]]:=cha;
          cha:=con;
          con:=cha shl 1;
     end;
     h[cha]:=y; g[cha]:=x;
     p[x,y]:=cha;
end;

procedure pr;
var i,j,x,y:longint; val:real;
begin
     f[k,1]:=0;
     for i:=0 to k-1 do d[i,1]:=true;
     update(k,1);
     repeat
           pop(x,y);
           d[x,y]:=true;
           if y=n then
           begin
                writeln(f[x,y]:0:2);
                exit;
           end;
           for i:=0 to x do
             for j:=pos[y] to pos[y+1]-1 do
               if not d[i,a[j]] and (f[i,a[j]]>f[x,y]+v[j]/pow[x-i]) then
               begin
                    f[i,a[j]]:=f[x,y]+v[j]/pow[x-i];
                    update(i,a[j]);
               end;
     until false;
end;

begin
     assign(input,fi); reset(input);
     rf;
     init;
     pr;
     close(input);
end.

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 1001;
const int K = 11;
const int oo = 2000000000;
using namespace std;
vector< pair<int, double> > a[N];
double d[N][K];
bool chk[N][K];
int n, m, k;
int main()
{
    //freopen("NETACCEL.in", "r", stdin);
    scanf("%d %d %d\n", &n, &m, &k);
    int i, x, y, c;
    for(i=1; i<=m; i++) {
        scanf("%d %d %d\n", &x, &y ,&c);
        a[x].push_back(make_pair(y, c));
        a[y].push_back(make_pair(x, c));
    }
    int j;
    for(i=1; i<=n; i++)
        for(j=0; j<=k; j++)
        d[i][j] = oo;
    d[1][0] = 0;
    int u, v, uk; double uv, minD;
    while (true) {
        minD = oo;
        for(i=1; i<=n; i++)
            for(j=0; j<=k; j++)
                if ((!chk[i][j]) && minD > d[i][j]) {
                    minD = d[i][j];
                    u = i; uk = j;
                }
        if (u == n && uk == k) break;
        chk[u][uk] = true;
        for(i = 0; i < a[u].size(); i++) {
            v = a[u][i].first;
            uv = a[u][i].second;
            for(j = uk; j<=k; j++)
                d[v][j] = min(d[v][j], d[u][uk] + uv/(1 << (j - uk)));
        }
    }
    printf("%.2f", d[n][k]);
    return 0;
}

Code mẫu của RR

{$R-,Q-}
{$MODE OBJFPC}

uses math;
const
  FINP='';
  FOUT='';
  MAXN=1000;
  MAXK=10;
  oo=1000111*1024*MAXN;

type
  list=^node;
  node=record
        u,c:longint;
        next:list;
  end;

procedure add(u,c:longint; var a:list); inline;
    var
      p:list;
    begin
      new(p); p^.u:=u; p^.c:=c;
      p^.next:=a; a:=p;
    end;

var
  f1,f2:text;
  n,m,k:longint;
  ke:array[1..MAXN] of list;

  f:array[1..MAXN,0..MAXK] of int64;

  hsize:longint;
  hu,ht:array[1..2*MAXN*MAXK] of longint;
  hpos:array[1..MAXN,0..MAXK] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;

procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure inp;
    var
      u,v,c,i:longint;
    begin
      read(f1,n,m,k);
      for i:=1 to m do
        begin
          read(f1,u,v,c);
          add(u,c*1024,ke[v]);
          add(v,c*1024,ke[u]);
        end;
    end;

function lower(a,b:longint):boolean; inline;
    begin
      exit( f[hu[a],ht[a]] < f[hu[b],ht[b]] );
    end;

procedure swap(var a,b:longint); inline;
    var
      tmp:longint;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure swapH(a,b:longint); inline;
    begin
      swap(hpos[hu[a],ht[a]],hpos[hu[b],ht[b]]);
      swap(hu[a],hu[b]);
      swap(ht[a],ht[b]);
    end;

procedure downHeap(i:longint); inline;
    var
      j:longint;
    begin
      j:=i shl 1;
      while (j<=hsize) do
        begin
          if (j<hsize) and lower(j+1,j) then inc(j);
          if lower(j,i) then swapH(i,j)
          else break;
          i:=j; j:=i shl 1;
        end;
    end;

procedure upHeap(i:longint); inline;
    var
      j:longint;
    begin
      j:=i shr 1;
      while (i>1) and lower(i,j) do
        begin
          swapH(i,j);
          i:=j; j:=i shr 1;
        end;
    end;

procedure push(u,t:longint);
    begin
      inc(hsize);
      hu[hsize]:=u; ht[hsize]:=t;
      hpos[u,t]:=hsize;
      upHeap(hsize);
    end;

procedure pop(var u,t:longint);
    begin
      u:=hu[1]; t:=ht[1];
      swapH(1,hsize);
      hpos[hu[1],ht[1]]:=1;
      dec(hsize);
      downHeap(1);
    end;

procedure solve;
    var
      u,v,t,tt,c:longint;
      p:list;
    begin
      for u:=1 to n do
      for t:=0 to k do
        f[u,t]:=oo;

      f[1,0]:=0;
      push(1,0);
      while (hsize>0) do
        begin
          pop(u,t);
          if (u=n) then
            begin
              writeln(f2,f[u,t]/1024:0:2);
              exit;
            end;
          p:=ke[u];
          while p<>nil do
            begin
              v:=p^.u; c:=p^.c; p:=p^.next;
              for tt:=t to k do
                begin
                  if f[u,t]+c<f[v,tt] then
                    begin
                      f[v,tt]:=f[u,t]+c;
                      if hpos[v,tt]=0 then push(v,tt)
                      else upHeap(hpos[v,tt]);
                    end;
                  c:=c>>1;
                end;
            end; //for (v,c)
        end; //while (hsize>0)
    end; //solve

begin
  openF;
  inp;
  solve;
  closeF;
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, 0, -1, +1};
//const int dc[] = {-1, +1, 0, 0};
const int dr[] = {-2, -1, +1, +2, +2, +1, -1, -2};
const int dc[] = {+1, +2, +2, +1, -1, -2, -2, -1};

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const double eps = 1e-9;
const ll mod = 1000000000;
typedef pair<int, int> II;

#define maxn 1005
#define maxe 200005

using namespace std;

int n, m, k;
double cost[maxe], f[maxn][11];
int next[maxe], adj[maxe], last[maxn], E = 0;

void add(int u, int v, double c){
    adj[E] = v; cost[E] = c; next[E] = last[u]; last[u] = E++;
    adj[E] = u; cost[E] = c; next[E] = last[v]; last[v] = E++;
}

int main(){
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    scanf("%d %d %d", &n, &m, &k);
    int u, v, id; double c, t; E = 0; ms(last, -1);
    Rep(run, m){
        scanf("%d %d %lf", &u, &v, &c);
        add(u, v, c);
    }

    Rep(i, n + 1) Rep(j, k + 1) f[i][j] = double(inf);

    Rep(i, k + 1) f[1][i] = 0;
    priority_queue<pair<double, II> > que;
    que.push(mp(0, mp(1, 0)));
    while(!que.empty()){
        c = -que.top().fi; u = que.top().se.fi; id = que.top().se.se;
        que.pop();

        if(u == n) break;
        if(f[u][id] < c - eps) continue;
        for(int e = last[u]; e != -1; e = next[e]){
            v = adj[e];
            For(i, id, k){
                t = c + cost[e] / (1 << (i - id));
                if(f[v][i] > t){
                    f[v][i] = t;
                    que.push(mp(-f[v][i], mp(v, i)));
                }
            }
        }
    }
    printf("%.2lf\n", f[n][k]);

}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define INF 1e12
typedef long long ll;
using namespace std;

int n,m,k;
vector< pair<int,double> > adj[1010];
double d[1010][10];
bool chs[1010][10];

void Dijkstra()
{
     for (int i = 1; i <= n; i++)
       for (int j = 0; j <= k; j++)
         d[i][j] = (i == 1) ? 0.0 : INF;

     memset(chs,true,sizeof(chs));
     for (int i = 1; i <= k; i++) chs[1][i] = false;
     priority_queue < pair< double, pair<int,int> > > q;          
     q.push(make_pair( 0.0, make_pair(1,0)));

     while (!q.empty())
     {
           pair< double, pair<int,int> > pp = q.top();  q.pop();
           pair<int,int> qq = pp.second;
           int ux = qq.first,uy = qq.second;
           if (!chs[ux][uy]) continue;
           chs[ux][uy] = false;

           FOR(i,0,adj[ux].size())
           {
               int v = adj[ux][i].first;
               double temp = adj[ux][i].second * 2;

               FOR(j,uy,k + 1)
               {                          
                  temp /= 2;
                  if (chs[v][j] && d[v][j] > d[ux][uy] + temp)
                  {
                     d[v][j] = d[ux][uy] + temp;
                     pair< double, pair<int,int> > newp = make_pair( -d[v][j], make_pair(v,j) );
                     q.push(newp);
                  };                  
               };
           };           
     };
};

int main()
{
//    freopen("nac.in","r",stdin);
//    freopen("nac.ou","w",stdout);
    scanf("%d %d %d", &n, &m, &k);
    FOR(i,0,m)
    {
        int x,y;  double c;
        scanf("%d %d %lf", &x, &y, &c);
        adj[x].push_back(make_pair(y,c));
        adj[y].push_back(make_pair(x,c));
    };
    Dijkstra();
    printf("%.2lf\n", d[n][k]);
};

Code mẫu của khuc_tuan

type
    integer = longint;

    PList = ^List;
    List = record
         v, len : integer;
         next : PList;
    end;

    Node = record
        id, k : integer;
    end;

var
   n, m, k, nheap : integer;
   j, i, u, v, len : integer;
   ke : array[1..1000] of PList;
   d : array[1..1000,0..10] of double;
   heap : array[1..10000] of Node;
   position : array[1..1000,0..10] of integer;

function compare(a,b : Node) : integer;inline;
var
   dd : double;
begin
     dd := d[a.id][a.k] - d[b.id][b.k];
     if dd > 0 then compare := 1
     else if dd = 0 then compare := 0
     else if dd < 0 then compare := -1;
end;

procedure pushup(i : integer);
var
   j : integer;
   t : Node;
begin
    while i > 1 do
    begin
        j := i div 2;
        if compare(heap[i], heap[j]) < 0 then
        begin
            t := heap[i]; heap[i] := heap[j]; heap[j] := t;
            position[heap[i].id][heap[i].k] := i;
            // position[heap[j].id][heap[j].k] := j;
            i := j;
        end
        else break;
    end;
    position[heap[i].id][heap[i].k] := i;
end;

procedure pushdown(i : integer);
var
   j : integer;
   t : Node;
begin
    while 2 * i <= nheap do
    begin
        j := 2 * i;
        if (j < nheap) and (compare(heap[j+1],heap[j]) < 0) then inc(j);
        if compare(heap[i],heap[j]) > 0 then
        begin
            t := heap[i]; heap[i] := heap[j]; heap[j] := t;
            position[heap[i].id][heap[i].k] := i;
            // position[heap[j].id][heap[j].k] := j;
            i := j;
        end
        else break;
    end;
    position[heap[i].id][heap[i].k] := i;
end;

procedure addheap(n : Node);
begin
    inc(nheap);
    heap[nheap] := n;
    position[n.id][n.k] := nheap;
    pushup(nheap);
end;

procedure update(n : Node);
var p : integer;
begin
     p := position[n.id][n.k];
     pushup(p);
     pushdown(p);
end;

procedure delmin;
begin
     position[heap[1].id][heap[1].k] := -1;
     dec(nheap);
     if nheap > 0 then
     begin
         heap[1] := heap[nheap + 1];
         position[heap[1].id][heap[1].k] := 1;
         pushdown(1);
     end;
end;

procedure add(var p : PList; v, len : integer);
var
   q : PList;
begin
     new(q);
     q^.v := v;
     q^.len := len;
     q^.next := p;
     p := q;
end;

var
   node1, node2 : Node;
   ite : PList;
   dl, newlen : double;

begin
    read(n,m,k);
    for i:=1 to m do
    begin
        read(u,v,len);
        add( ke[u], v, len);
        add( ke[v], u, len);
    end;
    fillchar( position, sizeof(position), 255);
    for i:=1 to n do
        for j:=0 to k do
            d[i,j] := 1e11;
    d[1,k] := 0;
    node1.id := 1; node1.k := k;
    addheap(node1);
    while nheap > 0 do
    begin
        node1 := heap[1];
        delmin;
        ite := ke[node1.id];
        while ite <> nil do
        begin
             node2.id := ite^.v;
             dl := ite^.len;

             for j:=0 to node1.k do
             begin
                 newlen := dl + d[node1.id][node1.k];
                 node2.k := node1.k - j;
                 if newlen < d[node2.id][node2.k] then
                 begin
                      d[node2.id][node2.k] :=newlen;
                      if position[node2.id][node2.k] = -1 then
                         addheap(node2)
                      else
                         update(node2);
                 end;
                 dl := dl / 2;
             end;

             ite := ite^.next;
        end;
    end;
    writeln(d[n][0] : 0 : 2);
end.