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

#include <iostream>
#include <algorithm>
#include <cstdio>
#define oo 1000111222
using namespace std;

int n,x,d[111][111],visited[111];
long long ans;

int main()
{
    cin >> n;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            scanf("%d",&d[i][j]);
            if (!d[i][j]) d[i][j]=oo;
        }
    for (int k=1;k<=n;k++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    visited[x=1]=1;
    while (1)
    {
        int y=0,best=oo-1;
        for (int i=2;i<n;i++)
            if (!visited[i] && d[x][i]<best)
                best=d[x][i], y=i;
        if (!y) break;
        ans+=d[x][y]; visited[x=y]=1;           
    }
    ans+=d[x][n];
    cout << ans << endl;
}

Code mẫu của happyboy99x

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 111;
typedef pair<int, int> ii;
priority_queue<ii, vector<ii>, greater<ii> > a[N];
int n, c[N][N], vst[N];

void enter() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            scanf("%d",&c[i][j]), c[i][j] = c[i][j] == 0 ? 1000000000 : c[i][j];
}

void floyd() {
    for(int k = 1; k <= n; ++k)
        for(int u = 1; u <= n; ++u)
            for(int v = 1; v <= n; ++v)
                c[u][v] = min(c[u][k] + c[k][v], c[u][v]);
}

void solve() {
    for(int u = 1; u <= n; ++u)
        for(int v = 1; v < n; ++v)
            a[u].push(ii(c[u][v], v));
    int res = 0, u = 1;
    while(true) {
        vst[u] = 1; while(!a[u].empty() && vst[a[u].top().second]) a[u].pop();
        if(a[u].empty()) { res += c[u][n]; break; }
        else {
            int v = a[u].top().second;
            res += a[u].top().first; a[u].pop(); u = v;
        }
    }
    printf("%d\n", res);
}

int main() {
    enter();
    floyd();
    solve();
    return 0;
}

Code mẫu của ladpro98

program TTRIP;
uses    math;
const   maxn=101;
        fi='';
        oo=trunc(1e9);
var     a:array[1..maxn,1..maxn] of longint;
        chk:array[1..maxn] of boolean;
        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 begin
                read(inp,a[i,j]);
                if a[i,j]=0 then a[i,j]:=oo;
        end;
        close(inp);
end;

procedure floyd;
var     i,j,k:longint;
begin
        for k:=1 to n do
        for i:=1 to n do
        for j:=1 to n do
        a[i,j]:=min(a[i,j],a[i,k]+a[k,j]);
end;

procedure process;
var     res,s,i,j,m,minw:longint;

begin
        s:=1;res:=0;
        for i:=2 to n-1 do begin
                minw:=oo;m:=0;
                for j:=2 to n-1 do
                if (not chk[j]) and (a[s,j]<minw) then begin
                        m:=j;
                        minw:=a[s,j];
                end;
                if minw=oo then break;
                inc(res,minw);
                chk[m]:=true;
                s:=m;
        end;
        write(res+a[s,n]);
end;

begin
        input;
        floyd;
        process;
end.

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (REACHEOF) return 0;\
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);

int n, c[111][111], visited[111];

int main() {
    scanf("%d", &n);
    FOR(i,1,n) FOR(j,1,n) {
        scanf("%d", &c[i][j]);

        if (i != j && c[i][j] == 0) c[i][j] = 1000111000;
    }
    FOR(k,1,n)
        FOR(i,1,n) FOR(j,1,n)
            c[i][j] = min(c[i][j], c[i][k] + c[k][j]);

    int pos = 1, res = 0;
    visited[1] = true;
    while (pos != n) {
        int best = -1;
        FOR(next,2,n-1)
            if (!visited[next])
                if (best == -1 || c[pos][next] < c[pos][best] || (c[pos][next] == c[pos][best] && next < best)) {
                    best = next;
                }
        if (best == -1) best = n;

        res += c[pos][best];
        pos = best;
        visited[best] = true;
    }
    cout << res << endl;
    return 0;
}

Code mẫu của hieult

#pragma comment(linker, "/STACK:16777216")

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000001
#define maxn 2002
#define base 1000000000
#define modunlo 111539786
#define oo 1000000002
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define ull unsigned long long

double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

typedef long long int64;
int n, a[105][105], flag[105] = {0}, u = 1, v , kq = 0, MIN;

int main(){
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++){
        scanf("%d",&a[i][j]);
        if(!a[i][j]) a[i][j] = oo;
    }
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= n; k++){
        if(a[j][i] + a[i][k] < a[j][k]){
            a[j][k] = a[j][i] + a[i][k];
            a[k][j] = a[j][i] + a[i][k];
        }
    }
    flag[1] = 1;
    while(true){
        v = 0;
        MIN = oo;
        for(int i = 1; i < n; i++){
            if(a[u][i] < MIN && !flag[i]){
                v = i;
                MIN = a[u][i];
            }
        }
        if(v == 0){
            break;
        }
        else{
            kq += a[u][v];
            u = v;
            flag[u] = 1;
        }
    }
    kq += a[u][n];
    printf("%d",kq);
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

int n,a[105][105];
int INF = (1 << 30) - 5;
bool check[105];

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      scanf("%d", &a[i][j]);
      if (i != j && !a[i][j]) a[i][j] = INF;
    }

   for (int k = 0; k < n; k++)
     for (int i = 0; i < n; i++)
       for (int j = 0; j < n; j++)
         a[i][j] = min(a[i][j],a[i][k] + a[k][j]);

   int ret = 0,start = 0;
   for (int iter = 0; iter < n - 2; iter++) {
     int len = INF,pos;
     for (int j = 1; j < n - 1; j++) if (!check[j] && a[start][j] < len) {
       len = a[start][j];
       pos = j;
     }
     ret += len;
     check[pos] = true;
     start = pos;
   }
   printf("%d\n", ret + a[start][n - 1]);
}