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<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

const int N = 5000, T = 8, INF = 1e9;
int d[T][N], n, m, t;
vector<int> graph[N];

void enter() {
    cin >> n >> t >> m;
    for(int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        graph[u].push_back(v);
    }
}

void bfs(int s, int d[]) {
    queue<int> q; q.push(s);
    fill_n(d, n, -1); d[s] = 0;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(unsigned i = 0; i < graph[u].size(); ++i) {
            int v = graph[u][i];
            if(d[v] == -1) d[v] = d[u] + 1, q.push(v);
        }
    }
}

int solve() {
    for(int i = 0; i < t; ++i) bfs(i, d[i]);
    vector<int> perm;
    for(int i = 1; i < t; ++i) perm.push_back(i);
    if(perm.empty()) return 0;
    int res = INF;
    do {
        int cost = d[0][perm.front()] + d[perm.back()][0];
        for(unsigned i = 0; i + 1 < perm.size(); ++i)
            cost += d[perm[i]][perm[i + 1]];
        res = min(res, cost);
    } while(next_permutation(perm.begin(), perm.end()));
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    cout << solve();
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
const int N = 5555;
const int V = 1 << 9;
using namespace std;
vector<int> a[N], r;
bool was[N][V]; int d[N][V];
ii Q[N * V];
int n, m, t;

void BFS() {
    int l = 1, r = 1, i, u, bu, v, bv;
    Q[1] = ii(0, 0);
    was[0][0] = true;
    while (l <= r) {
        u = Q[l].X; bu = Q[l++].Y;
        for(i=0; i<a[u].size(); i++) {
            v = a[u][i]; bv = bu;
            if (v < t) bv = bv | (1 << v);
            if (!was[v][bv]) {
                Q[++r] = ii(v, bv);
                was[v][bv] = true;
                d[v][bv] = d[u][bu] + 1;
            }
        }
    }
}

int main()
{
    scanf("%d %d %d\n", &n, &t, &m);
    int i, u, v;
    for(i=1; i<=m; i++) {
        scanf("%d %d\n", &u, &v);
        a[u].push_back(v);
        if (v == 0) r.push_back(u);
    }
    BFS();
    cout << d[0][(1 << t) - 1];
    return 0;
}

Code mẫu của skyvn97

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define MAXN   5050
#define MAXS   259
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;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;
typedef pair<int,int> ii;
vector<int> g[MAXN];
int d[MAXN][MAXS];
int m,n,p;
void init(void) {
    scanf("%d",&n);
    scanf("%d",&p);
    scanf("%d",&m);
    REP(i,m) {
        int u,v;
        scanf("%d",&u);
        scanf("%d",&v);
        g[u+1].push_back(v+1);
    }
    memset(d,-1,sizeof d);
}
void BFS(void) {
    queue<ii> q;
    while (!q.empty()) q.pop();
    d[1][1]=0;
    q.push(ii(1,1));
    while (!q.empty()) {
        ii u=q.front();q.pop();
        if (u==ii(1,(1<<p)-1)) {
            printf("%d",d[u.fi][u.se]);
            return;
        }
        FORE(it,g[u.fi]) {
            int tmp=u.se;
            if (*it<=p) tmp=tmp|(1<<(*it-1));
            if (d[*it][tmp]<0) {
                d[*it][tmp]=d[u.fi][u.se]+1;
                q.push(ii(*it,tmp));
            }
        }
    }
}
int main(void) {
    init();
    BFS();
    return 0;
}