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

uses math;
const fi='';
      oo=100000000;
var m,n,k,num,s,t:longint;
    a,tr:array[1..100,1..100] of longint;
    re:array[1..100] of longint;

procedure rf;
var i,x,y,c:longint;
begin
        read(n,m,k);
        for x:=1 to n-1 do
          for y:=x+1 to n do
          begin
                a[x,y]:=oo;
                tr[x,y]:=y;
                a[y,x]:=oo;
                tr[y,x]:=x;
          end;
        for x:=1 to n do tr[x,x]:=x;
        for i:=1 to m do
        begin
                read(x,y,c);
                a[x,y]:=min(a[x,y],c);
                a[y,x]:=min(a[y,x],c);
        end;
end;

procedure pr;
var i,j,k:longint;
begin
        for k:=1 to n do
          for i:=1 to n do
            for j:=1 to n do
              if a[i,j]>a[i,k]+a[k,j] then
              begin
                   a[i,j]:=a[i,k]+a[k,j];
                   tr[i,j]:=tr[i,k];
              end;
end;

procedure wf;
var i,j,z:longint;
begin
        for i:=1 to k do
        begin
                read(z,s,t);
                if z=0 then writeln(a[s,t])
                else
                begin
                     num:=1; re[1]:=s;
                     repeat
                           s:=tr[s,t];
                           inc(num);
                           re[num]:=s;
                     until t=s;
                     write(num);
                     for j:=1 to num do write(' ',re[j]);
                     writeln;
                end;
        end;
end;

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

Code mẫu của happyboy99x

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

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;

#define TR(v, it) for(typeof((v).begin()) it = (v).begin(), _e = (v).end(); it != _e; ++it )
#define INF 1000000000

vvii g;
int t[105][105], d[105][105];
int n, m, k;

void dijkstra( vvii & g, int s, int d[], int t[] ) {
    priority_queue<ii> q; q.push(ii(0, s));
    for( int i = 0; i < n; ++i ) d[i] = INF;
    d[s] = 0; t[s] = s;
    while( !q.empty() ) {
        int du = q.top().first, u = q.top().second; q.pop();
        if (du > d[u]) continue;
        TR(g[u], it) {
            int v = it->first, l = it->second;
            if (d[v] > du + l) {
                d[v] = du + l; t[v] = u;
                q.push(ii(d[v], v));
            }
        }
    }
}

int main() {
    scanf( "%d%d%d", &n, &m, &k );
    g = vvii(n, vii());
    while(m--) {
        int u, v, l; scanf( "%d%d%d", &u, &v, &l );
        g[--u].push_back(ii(--v, l));
        g[v].push_back(ii(u, l));
    }
    for( int i = 0; i < n; ++i ) dijkstra(g, i, d[i], t[i]);
    while(k--) {
        int q, u, v; scanf( "%d%d%d", &q, &u, &v );
        --u; --v;
        if(q) {
            stack<int> st; int x = v; st.push(x);
            do {
                x = t[u][x];
                st.push(x);
            } while( x != u );
            printf( "%d", st.size() );
            while(!st.empty()) {
                printf( " %d", st.top()+1 );
                st.pop();
            }
            printf("\n");
        } else printf("%d\n", d[u][v]);
    }
    return 0;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 101;
const int oo = 1000000009;
using namespace std;
int a[N][N], T[N][N];
int n, m, Q;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> Q;
    REP(i, 1, n) REP(j, 1, n)
    if (i != j) a[i][j] = oo;
    REP(i, 1, n) T[i][i] = i;
    int u, v, c, kind;
    FOR(i, 0, m) {
        cin >> u >> v >> c;
        a[u][v] = a[v][u] = c;
        T[u][v] = v; T[v][u] = u;
    }
    REP(k, 1, n) REP(i, 1, n) REP(j, 1, n)
    if (a[i][j] > a[i][k] + a[k][j]) {
        a[i][j] = a[i][k] + a[k][j];
        T[i][j] = T[i][k];
    }
    while (Q--) {
        cin >> kind >> u >> v;
        if (kind == 0) cout << (a[u][v] >= oo ? -1 : a[u][v]) << '\n';
        else {
            if (u == v) {
                cout << "2 " << u << ' ' << v << '\n';
                continue;
            }
            VI path;
            while (u != v) {
                path.PB(u);
                u = T[u][v];
            }
            cout << SZ(path) + 1 << ' ';
            TR(it, path) cout << *it << ' '; cout << v;
            cout << '\n';
        }
    }
    return 0;
}

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       111;

var
  f1,f2         :       text;
  n,m,k         :       longint;
  c,trace       :       array[1..MAXN,1..MAXN] 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
      i,u,v:longint;
    begin
      read(f1,n,m,k);
      for u:=1 to n do
      for v:=1 to n do
        c[u,v]:=1000111000;
      for i:=1 to m do
        begin
          read(f1,u,v,c[u,v]);
          c[v,u]:=c[u,v];
        end;
      for i:=1 to n do c[i,i]:=0;
    end;

procedure init;
    var
      i,j,k:longint;
    begin
      for i:=1 to n do
      for j:=1 to n do
        trace[i,j]:=j;

      for k:=1 to n do
        for i:=1 to n do
        for j:=1 to n do
          if c[i,j]>c[i,k]+c[k,j] then
            begin
              c[i,j]:=c[i,k]+c[k,j];
              trace[i,j]:=trace[i,k];
            end;
    end;

procedure solve;
    var
      i,q,u,v,count:longint;
    begin
      for i:=1 to k do
        begin
          read(f1,q,u,v);
          if q=0 then writeln(f2,c[u,v])
          else
            begin
              count:=1; q:=u;
              repeat
                inc(count);
                u:=trace[u,v];
              until u=v;
              write(f2,count,' ',q);
              u:=q;
              repeat
                u:=trace[u,v];
                write(f2,' ',u);
              until u=v;
              writeln(f2);
            end;
        end;
    end;

begin
  openF;
  inp;
  init;
  solve;
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#define max 1000
#define maxEC 1000
#define maxC max*maxEC
long c[max][max],Trace[max][max],n,a,b,T,x;
//FILE *p;
void Enter()
{
//p=fopen("D:\\Hoc tap\\test\\FLOYD\\FLOYD.IN0","r");    
long m,u,v;
scanf("%ld %ld %ld",&n,&m,&T);
for(long u=1;u<=n;u++)
  for(long v=1;v<=n;v++)
    {
    if(u==v) c[u][v]=0;
    else c[u][v]=maxC;
    }
for(long i=1;i<=m;i++)
  {
  scanf("%ld %ld",&u,&v);
  scanf("%ld",&c[u][v]);
  c[v][u]=c[u][v];
  }
}
void Floyd()
{
for(long u=1;u<=n;u++)
  for(long v=1;v<=n;v++)
    Trace[u][v]=v;
for(long k=1;k<=n;k++)
  for(long u=1;u<=n;u++)
    for(long v=1;v<=n;v++)
      if(c[u][v]>c[u][k]+c[k][v])
        {
        c[u][v]=c[u][k]+c[k][v];
        Trace[u][v]=Trace[u][k];
        }
}
void Result()
{
for(long i=1;i<=T;i++)
  {
  scanf("%ld %ld %ld",&x,&a,&b);
  if(c[a][b]==maxC)
    printf("-1\n");
  else
    {    
    if(x==0) printf("%ld\n",c[a][b]);
    else 
      {
      long t=1;
      long d=a;     
      do
        {
        d=Trace[d][b];
        t++;
        }while(d!=b);
      printf("%ld ",t);
      do
        {
        printf("%ld ",a);
        a=Trace[a][b];
        }while(a!=b); 
      printf("%ld\n",b);   
      }
    }
  }
}     
main()
{
Enter();
Floyd();
Result();
//getch();
}

Code mẫu của ll931110

Program FLOYD;
        Const
                input  = '';
                output = '';
        Var
                F,Trace: array[1..100,1..100] of longint;
                  n,m,k: longint;
                    val: array[1..100] of longint;
                  fi,fo: text;

Procedure LoadGraph;
          Var
                i,j,u,v: longint;
          Begin
                Assign(fi, input);
                        Reset(fi);
                                Readln(fi, n, m, k);

                                For i:= 1 to n do
                                        For j:= 1 to n do if i = j then F[i,j]:= 0
                                                                   else F[i,j]:= 10000000;

                                For i:= 1 to m do
                                        Begin
                                                Readln(fi, u,v,F[u,v]);
                                                F[v,u]:= F[u,v];
                                        End;
          End;

Procedure Floyd;
          Var
                k,u,v: longint;
          Begin
                For u:= 1 to n do
                        For v:= 1 to n do Trace[u,v]:= v;

                For k:= 1 to n do
                        For u:= 1 to n do
                                For v:= 1 to n do
                                        if F[u,v] > F[u,k] + F[k,v] then
                                                Begin
                                                        F[u,v]:= F[u,k] + F[k,v];
                                                        Trace[u,v]:= Trace[u,k];
                                                End;
          End;

Procedure PrintResult;
          Var
                x,u,v,i,j,num: longint;
          Begin
                Assign(fo, output);
                        Rewrite(fo);
                                For i:= 1 to k do
                                        Begin
                                                Readln(fi, x, u, v);

                                                If x = 0 then writeln(fo, F[u,v]);
                                                If x = 1 then
                                                        Begin
                                                                num:= 0;

                                                                Repeat
                                                                        inc(num);
                                                                        val[num]:= u;
                                                                        u:= Trace[u, v];
                                                                Until u = v;

                                                                inc(num);
                                                                Write(fo, num, ' ');

                                                                For j:= 1 to num - 1 do write(fo, val[j], ' ');
                                                                Writeln(fo, v);
                                                        End;
                                        End;
                        Close(fo);
                Close(fi);
          End;

Begin
        LoadGraph;
        Floyd;
        PrintResult;
End.

Code mẫu của skyvn97

const     INP        =        '' ;
          OUT        =        '' ;

          maxn       =        100      ;
          maxc       =        10000000 ;

var       n , m , cau_hoi :  integer ;
          a          :       array[1..maxn,1..maxn] of longint ;
          trace      :       array[1..maxn,1..maxn] of byte    ;
          fi , fo    :       text    ;

procedure answer ;
var
      i , j , u , v , pt , loai : integer ;
      l : array[1..maxn] of integer ;

      procedure truy_vet( u , v : integer ) ;
      var
           k : integer ;
      begin
           k := trace[u,v] ;
           if k = 0 then begin
              inc( pt )  ;
              l[pt] := v ;
              exit ;
           end ;
           truy_vet( u , k ) ;
           truy_vet( k , v ) ;
      end ;

begin
     for i := 1 to cau_hoi do begin
         read( fi , loai , u , v ) ;
         if loai = 0 then writeln( fo , a[u,v] ) { cau hoi loai 0 }
         else
             { cau hoi loai 1 }
             if a[u,v] < 0 then writeln( fo , -1 )
             else begin
                 pt   := 1 ;
                 l[1] := u ;
                 truy_vet( u , v ) ;

                 write( fo , pt )  ;
                 for j := 1 to pt do write( fo , ' ', l[j] ) ;
                 writeln( fo ) ;
             end ;
     end ;
end ;

procedure process ;
var
     k , u,  v : longint ;
begin
     for k := 1 to n do { Floyd }
         for u := 1 to n do
             for v := u + 1 to n do
                 if a[u,v] > a[u,k] + a[k,v] then begin
                    a[u,v] := a[u,k] + a[k,v] ;
                    a[v,u] := a[u,v] ;
                    trace[u,v] := k  ;
                    trace[v,u] := k  ;
                 end ;

     for u := 1 to n do
         for v := 1 to n do
             if a[u,v] = maxc then a[u,v] := -1 ; { Khong ton tai duong di }
end ;

procedure nhapdl ;
var
      i , j,  u , v , val : longint ;
begin
     read( fi , n , m , cau_hoi ) ;
     for i := 1 to n do
         for j := 1 to n do a[i,j] := maxc ;
     for i := 1 to m do begin
         read( fi , u , v , val ) ;
         a[u,v] := val ;
         a[v,u] := val ;
     end ;

     for i := 1 to n do a[i,i] := 0 ;
end ;

procedure mofile ;
begin
     assign( fi , INP ) ; reset( fi )   ;
     assign( fo , OUT ) ; rewrite( fo ) ;
end ;

procedure dongfile ;
begin
     close( fi ) ; close( fo ) ;
end ;

BEGIN
     mofile   ;
     nhapdl   ;
     process  ;
     answer   ;
     dongfile ;
END.

Code mẫu của khuc_tuan

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <cstdlib>
#include <ctime>
#include <string.h>

const int maxN = 100010;
const int oo = 1000000000;

using namespace std;

int n, m, kk, nheap;
int head[maxN], ke[maxN], next[maxN], ts[maxN], kq[maxN], h[maxN], pos[maxN], d[maxN], truoc[maxN];

void Doc(){
    int x, y, z;
    scanf("%d%d%d", &n, &m, &kk);
    for(int i = 1; i <= m; i++){
        scanf("%d%d%d", &x, &y, &z);
        ke[i] = y;
        next[i] = head[x];
        head[x] = i;
        ts[i] = z;
        ke[i + m] = x;
        next[i + m] = head[y];
        head[y] = i + m;
        ts[i + m] = z;
    }
}

void Doicho(int &x, int &y){
    int tg = x;
    x = y;
    y = tg;
}

void Upheap(int i){
    if ((i == 1) || (d[h[i / 2]] < d[h[i]])) return;
    Doicho(h[i], h[i / 2]);
    Doicho(pos[h[i]], pos[h[i / 2]]);
    Upheap(i / 2);
}

void Downheap(int i){
    int j = 2 * i;
    if (j > nheap) return;
    if (j < nheap && d[h[j]] > d[h[j + 1]]) j++;
    if (d[h[i]] > d[h[j]]){
        Doicho(h[i], h[j]);
        Doicho(pos[h[i]], pos[h[j]]);
        Downheap(j);
    }
}

void Pus(int x){
    nheap++;
    h[nheap] = x;
    pos[x] = nheap;
    Upheap(nheap);
}

int Pop(){
    int tg = h[1];
    h[1] = h[nheap];
    pos[h[1]] = 1;
    nheap--;
    Downheap(1);
    return tg;
}

void Dijkstra(int u){
    int j, v;
    nheap = 0;
    for(int i = 1; i <= n; i++){
        pos[i] = 0;
        truoc[i] = 0;
    }
    for(int i = 1; i <= n; i++) d[i] = oo;
    d[u] = 0;
    Pus(u);
    do{
        if (nheap == 0) break;
        u = Pop();
      //  cout << u << " " << d[u] <<  endl;
        j = head[u];
        while (j != 0){
            v = ke[j];
            if (d[v] > d[u] + ts[j]){
                d[v] = d[u] + ts[j];
                truoc[v] = u;
                if (pos[v] == 0) Pus(v);
                else Upheap(pos[v]);
            }
            j = next[j];
        }
    }
    while (true);
}

void Lam(){
    int x, u, v, len;
    for(int i = 1; i <= kk; i++){
        scanf("%d%d%d", &x, &u, &v);
        //cin >> x >> u >> v;
        Dijkstra(u);
        if (x == 0) printf("%d\n", d[v]);
        else{
            len = 0;
            while (v != u){
                len++;
                kq[len] = v;
                v = truoc[v];
            }
            len++;
            kq[len] = u;
            cout << len << " ";
            for(int i = len; i >= 1; i--) cout << kq[i] << " ";
            printf("\n");
        }
    }
}

void Inkq(){
}


int main()
{
    //freopen("Floyd.inp", "r", stdin);
    //freopen("Floyd.out", "w", stdout);
    Doc();
    Lam();
    Inkq();
    return 0;
}