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 happyboy99x

#include <bits/stdc++.h>
using namespace std;

const long long LINF = (long long) 1e18;
const int N = (int) 1e5;
const int K = 5;
long long dist[N][K + 1];
vector<pair<int, int> > graph[N];
priority_queue<pair<long long, pair<int, int> > > q;

void update(int x, int y, long long cost) {
    if (cost < dist[x][y]) {
        dist[x][y] = cost;
        q.push(make_pair(-cost, make_pair(x, y)));
    }
}

int main() {
    ios::sync_with_stdio(false);
    int n; cin >> n;
    int m; cin >> m;
    int k; cin >> k;
    int s; cin >> s; --s;
    int t; cin >> t; --t;
    for (int i = 0; i < m; ++i) {
        int u; cin >> u; --u;
        int v; cin >> v; --v;
        int c; cin >> c;
        graph[u].push_back(make_pair(v, c));
        graph[v].push_back(make_pair(u, c));
    }
    memset(dist, 0x3f, sizeof dist);
    update(s, 0, 0);
    long long result = LINF;
    while (!q.empty()) {
        long long cost = -q.top().first;
        int u = q.top().second.first;
        int free = q.top().second.second;
        q.pop();
        if (cost != dist[u][free]) continue;
        if (u == t) result = min(result, cost);
        for (int i = 0; i < (int) graph[u].size(); ++i) {
            int v = graph[u][i].first;
            int c = graph[u][i].second;
            update(v, free, cost + c);
            if (free + 1 <= k) update(v, free + 1, cost);
        }
    }
    cout << result << '\n';
    return 0;
}

Code mẫu của ladpro98

#include <iostream>
#include <cstdio>
#include <queue>
#include <climits>
#include <vector>
#define REP(i, a, b) for (int i = (a); i <= (b); ++i)
#define II pair<int, int>
#define VII vector<II>
#define MP make_pair
#define X first
#define Y second
#define PB push_back

const int N = 100005;
const long long INF = 1000000000000000LL;

using namespace std;

struct vertex {
  int node, use; long long dist;
  vertex(int _node, int _use, long long _dist) {
    node = _node; use = _use; dist = _dist;
  }
  bool operator < (const vertex &that) const {
    return dist > that.dist;
  }
};

priority_queue<vertex> Q;
int n, m, k, s, t;
VII a[N];
long long d[N][6];

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  #ifdef _LAD_
    freopen("DHFRBUS.inp", "r", stdin);
  #endif // _LAD_
  cin >> n >> m >> k >> s >> t;
  int u, v, c;
  REP(i, 1, m) {
    cin >> u >> v >> c;
    a[u].PB(MP(v, c)); a[v].PB(MP(u, c));
  }
  REP(i, 1, n) REP(j, 0, k) d[i][j] = INF;
  Q.push(vertex(s, 0, 0)); d[s][0] = 0;
  long long ans = 0;
  while (!Q.empty()) {
    vertex u = Q.top(); Q.pop();
    if (u.dist != d[u.node][u.use]) continue;
    if (u.node == t) {
      ans = u.dist;
      break;
    }
    for (auto e: a[u.node])
      REP(use, u.use, u.use + (u.use < k)) {
        vertex v (e.X, use, u.dist + (use > u.use ? 0 : e.Y));
        if (d[v.node][v.use] > v.dist) {
          d[v.node][v.use] = v.dist;
          Q.push(v);
        }
      }
  }
  cout << ans << endl;
  return 0;
}

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   100100
#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 FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define fi   first
#define se   second
using namespace std;
struct State {
    int u,c;
    long long dis;
    State() {
        u=c=dis=0;
    }
    State(int _u,int _c,long long _dis) {
        u=_u;c=_c;dis=_dis;
    }
    bool operator < (const State &x) const {
        return (dis>x.dis);
    }
};
vector<pair<int,int> > adj[MAX];
long long dis[MAX][7];
int n,m,lim,s,t;
void loadGraph(void) {
    scanf("%d%d%d%d%d",&n,&m,&lim,&s,&t);
    REP(love,m) {
        int u,v,c;
        scanf("%d%d%d",&u,&v,&c);
        adj[u].push_back(make_pair(v,c));
        adj[v].push_back(make_pair(u,c));
    }
}
void dijkstra(void) {
    memset(dis,0x3f,sizeof dis);
    priority_queue<State> q;
    dis[s][0]=0;
    q.push(State(s,0,0));
    while (!q.empty()) {
        State cur=q.top();q.pop();
        if (dis[cur.u][cur.c]<cur.dis) continue;
        if (cur.u==t) {
            cout<<cur.dis<<endl;
            return;
        }
        FORE(it,adj[cur.u]) REP(j,2) if (cur.c+j<=lim) {
            int v=it->fi;
            if (dis[v][cur.c+j]>cur.dis+(j?0:it->se)) {
                dis[v][cur.c+j]=cur.dis+(j?0:it->se);
                q.push(State(v,cur.c+j,dis[v][cur.c+j]));
            }
        }
    }
    assert(false);
}
int main(void) {
    loadGraph();
    dijkstra();
    return 0;
}