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='';
      fo='';
      maxn=111;
      maxc=1000000000;
var n,s,f,res1,res2:longint;
    a:array[1..maxn,1..maxn] of longint;
    d,tr,r1,r2:array[0..maxn] of longint;
    free:array[1..maxn] of boolean;
    dau:array[1..maxn,1..maxn] of boolean;

procedure rf;
var i,x,y,t,m:longint;
begin
     assign(input,fi); reset(input);
     read(n,m,s,f);
     for x:=1 to n do
         for y:=1 to n do
             dau[x,y]:=false;
     for i:=1 to m do
     begin
          readln(x,y,t);
          if not dau[x,y] or (a[x,y]>t) then
          begin
               a[x,y]:=t; a[y,x]:=t;
               dau[x,y]:=true; dau[y,x]:=true;
          end;
     end;
     close(input);
end;

procedure dijk;
var i,j,x,min:longint;
begin
     for i:=1 to n do
     begin
          free[i]:=true;
          d[i]:=maxc;
          tr[i]:=i;
     end;
     x:=s; d[x]:=0; free[x]:=false;
     repeat
           for i:=1 to n do
               if free[i] and dau[x,i] and (d[i]>d[x]+a[x,i]) then
               begin
                    d[i]:=d[x]+a[x,i];
                    tr[i]:=x;
               end;
           j:=0; min:=maxc-1;
           for i:=1 to n do
               if free[i] and (d[i]<min) then
               begin
                    min:=d[i];
                    j:=i;
               end;
           x:=j; free[x]:=false;
     until not free[f];
     repeat
           j:=tr[x];
           dau[j,x]:=false; a[x,j]:=-a[x,j];
           x:=j;
     until x=s;
     res1:=d[f];
end;

procedure ford;
var i,x,y:longint; kt:boolean;
begin
     for i:=1 to n do
     begin
          d[i]:=maxc;
          tr[i]:=i;
     end;
     d[s]:=0;
     for i:=1 to n-1 do
     begin
          kt:=false;
          for y:=1 to n do
              for x:=1 to n do
                  if dau[y,x] and (d[x]>d[y]+a[y,x]) then
                  begin
                       d[x]:=d[y]+a[y,x];
                       tr[x]:=y;
                       kt:=true;
                  end;
          if not kt then break;
     end;
     x:=f;
     repeat
           y:=tr[x];
           dau[y,x]:=false;
           x:=y;
     until x=s;
     res2:=d[f];
end;

procedure pr;
var i,x,y:longint;
begin
     dijk;
     ford;
     for x:=1 to n-1 do
         for y:=x+1 to n do
             if dau[x,y] and dau[y,x] then
             begin
                  dau[x,y]:=false;
                  dau[y,x]:=false;
             end;
     r1[0]:=1; r2[0]:=1;
     r1[1]:=f; r2[1]:=f;
     x:=f;
     repeat
           for i:=1 to n do
               if dau[x,i] then break;
           inc(r1[0]);
           r1[r1[0]]:=i;
           dau[x,i]:=false;
           x:=i;
     until x=s;
     x:=f;
     repeat
           for i:=1 to n do
               if dau[x,i] then break;
           inc(r2[0]);
           r2[r2[0]]:=i;
           dau[x,i]:=false;
           x:=i;
     until x=s;
end;

procedure wf;
var i:longint;
begin
     assign(output,fo); rewrite(output);
     writeln(res1+res2);
     write(r1[0],' ');
     for i:=r1[0] downto 1 do write(r1[i],' ');
     writeln;
     write(r2[0],' ');
     for i:=r2[0] downto 1 do write(r2[i],' ');
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

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

typedef pair<int, int> ii;
#define N 100
int c[N][N], d[N], t[N], n, m, s, f;

void enter() {
    scanf("%d%d%d%d",&n,&m,&s,&f);
    --s; --f;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            c[i][j] = INT_MAX;
    for(int i = 0; i < m; ++i) {
        int u, v, l; scanf("%d%d%d",&u,&v,&l);
        --u; --v; c[u][v] = c[v][u] = l;
    }
}

int Dijkstra() {
    priority_queue<ii, vector<ii>, greater<ii> > qu;
    fill(d, d+n, INT_MAX); d[s] = 0; t[s] = -1;
    qu.push(ii(0, s));
    while(!qu.empty()) {
        int du = qu.top().first, u = qu.top().second; qu.pop();
        if(du > d[u]) continue;
        for(int v = 0; v < n; ++v)
            if(c[u][v] != INT_MAX && du + c[u][v] < d[v]) {
                qu.push(ii(d[v] = du + c[u][v], v));
                t[v] = u;
            }
    }
    for(int v = f; t[v] != -1; v = t[v]) {
        c[v][t[v]] = -c[v][t[v]];
        c[t[v]][v] = INT_MAX;
    }
    return d[f];
}

int FordBellman() {
    fill(d, d+n, INT_MAX); d[s] = 0; t[s] = -1;
    for(int step = 0, stop = 0; step < n-1 && !stop; ++step) {
        stop = 1;
        for(int u = 0; u < n; ++u) if(d[u] != INT_MAX)
            for(int v = 0; v < n; ++v) if(c[u][v] != INT_MAX && d[u] + c[u][v] < d[v]) {
                d[v] = d[u] + c[u][v];
                t[v] = u;
                stop = 0;
            }
    }
    for(int v = f; t[v] != -1; v = t[v]) c[t[v]][v] = INT_MAX; 
    return d[f];
}

void EditGraph() {
    for(int i = 0; i < n; ++i)
        for(int j = i + 1; j < n; ++j)
            if(c[i][j] != INT_MAX && c[j][i] != INT_MAX)
                c[i][j] = c[j][i] = INT_MAX;
}

stack<int> st;
void dfs(int u) {
    if(u == s) {
        printf("%d %d", st.size() + 1, s+1);
        for(; !st.empty(); st.pop()) printf(" %d", st.top()+1);
        printf("\n");
    } else
        for(int v = 0; v < n; ++v)
            if(c[u][v] != INT_MAX) {
                st.push(u);
                dfs(v);
            }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    enter();
    printf("%d\n", Dijkstra() + FordBellman());
    EditGraph();
    dfs(f);
    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 <fstream>
#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 RESET(a, v) memset(a, (v), sizeof(a))
#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>
#define VII vector<II>
#define endl '\n'

const int N = 111;
const int INF = INT_MAX;

using namespace std;

int T[N], d[N];
bool inQ[N], was[N];
int cost[N][N], cap[N][N], flow[N][N];
int n, m, source, sink, minCost, maxFlow;

bool findPath() {
  queue<int> Q;
  REP(i, 1, n) {
    T[i] = 0; d[i] = INF; inQ[i] = 0;
  }
  Q.push(source); d[source] = 0; inQ[source] = 1;
  while (!Q.empty()) {
    int u = Q.front(); Q.pop(); inQ[u] = 0;
    REP(v, 1, n)
    if (flow[u][v] < cap[u][v]) {
      int uv = cost[u][v] * (flow[u][v] < 0 ? -1 : 1);
      if (d[v] > d[u] + uv) {
        T[v] = u;
        d[v] = d[u] + uv;
        if (!inQ[v]) {
          inQ[v] = 1;
          Q.push(v);
        }
      }
    }
  }
  return d[sink] < INF;
}

void incFlow() {
  int delta = INF;
  for (int v = sink; v != source; v = T[v])
    delta = min(delta, flow[T[v]][v] < 0 ? -flow[T[v]][v] : (cap[T[v]][v] - flow[T[v]][v]));
  for (int v = sink; v != source; v = T[v])
    flow[T[v]][v] += delta, flow[v][T[v]] -= delta;
  maxFlow += delta;
  minCost += delta * d[sink];
}

VI path;

void showPath(int u) {
  path.PB(u);
  was[u] = 1;
  REP(v, 1, n)
  if (flow[u][v] > 0 && !was[v]) {
    showPath(v); break;
  }
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  #ifdef _LAD_
    freopen("HIWAY.in", "r", stdin);
  #endif // _LAD_
  cin >> n >> m >> source >> sink;
  int u, v;
  FOR(i, 0, m) {
    cin >> u >> v; cin >> cost[u][v];
    cost[v][u] = cost[u][v];
    cap[u][v] = cap[v][u] = 1;
  }
  ++n;
  cap[n][source] = 2;
  int S = source; source = n;
  while (findPath()) incFlow();
  if (maxFlow < 2) cout << -1 << endl;
  else {
    cout << minCost << endl;
    showPath(S);
    cout << SZ(path) << ' ';
    for (int it: path) cout << it << ' '; cout << endl;
    was[sink] = 0; path.clear();
    showPath(S);
    cout << SZ(path) << ' ';
    for (int it: path) cout << it << ' '; cout << endl;
  }
  return 0;
}

Code mẫu của RR

var
  cnt,res,k,u,v,n,m,s,t,ss:longint;
  fl,a,c,trace:array[1..111,1..111] of longint;
  kq:array[1..111] of longint;

procedure print(s:longint);
    var
      u:longint;
    begin
      inc(cnt); kq[cnt]:=s;
      if s=t then exit;
      for u:=1 to n do
        if fl[s,u]=1 then
          begin
            fl[s,u]:=0;
            print(u);
            exit;
          end;
    end;

begin
  read(n,m,s,t);

  for u:=1 to n do
  for v:=1 to n do
    begin
      a[u,v]:=1000111000;
      if u=v then a[u,v]:=0;
      trace[u,v]:=v;
    end;

  for m:=1 to m do
    begin
      read(u,v,a[u,v]);
      a[v,u]:=a[u,v];
    end;

  c:=a;
  for k:=1 to n do
    for u:=1 to n do
    for v:=1 to n do
      if c[u,v]>c[u,k]+c[k,v] then
        begin
          c[u,v]:=c[u,k]+c[k,v];
          trace[u,v]:=trace[u,k];
        end;
  res:=c[s,t];

  ss:=s;
  while ss<>t do
    begin
      fl[ss,trace[ss,t]]:=1;
      a [trace[ss,t],ss]:=-a[ss,trace[ss,t]];
      a [ss,trace[ss,t]]:=1000111000;
      ss:=trace[ss,t];
    end;

  c:=a;
  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 c[u,v]>c[u,k]+c[k,v] then
        begin
          c[u,v]:=c[u,k]+c[k,v];
          trace[u,v]:=trace[u,k];
        end;
  res:=res+c[s,t];

  ss:=s;
  while ss<>t do
    begin
      if c[ss,trace[ss,t]]<0 then fl[trace[ss,t],ss]:=0
      else fl[ss,trace[ss,t]]:=1;
      ss:=trace[ss,t];
    end;

  writeln(res);
  print(s);
  write(cnt); for u:=1 to cnt do write(' ',kq[u]); writeln;
  cnt:=0;
  print(s);
  write(cnt); for u:=1 to cnt do write(' ',kq[u]); writeln;
end.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   111
#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;
const int INF=(int)1e9+7;
typedef pair<int,int> ii;
void minimize(int &x,const int &y) {
    if (x>y) x=y;
}
class MaxFlowMinCost {
    public:
    struct edge {
        int from,to,capa,flow,cost;
        edge() {
            from=0;to=0;capa=0;flow=0;cost=0;
        }
        edge(int u,int v,int ca,int co) {
            from=u;to=v;capa=ca;flow=0;cost=co;
        }
        int residual(void) const {
            return (capa-flow);
        }       
    };
    vector<vector<int> > g;
    vector<edge> e;
    vector<int> d,tr;
    int n;  
    MaxFlowMinCost() {
        n=0;
    }
    MaxFlowMinCost(int n) {
        this->n=n;
        g.assign(n+7,vector<int>());
        e.clear();
        d=vector<int>(n+7);
        tr=vector<int>(n+7);
    }
    void addedge(int u,int v,int ca,int co) {
        g[u].push_back(e.size());
        e.push_back(edge(u,v,ca,co));
        g[v].push_back(e.size());
        e.push_back(edge(v,u,0,-co));
    }
    bool FordBellman(int s,int t) {
        FOR(i,1,n) {
            d[i]=INF;
            tr[i]=-1;
        }
        vector<bool> inq=vector<bool>(n+7,false);
        queue<int> q;
        while (!q.empty()) q.pop();
        q.push(s);d[s]=0;inq[s]=true;
        while (!q.empty()) {
            int u=q.front();q.pop();inq[u]=false;
            FORE(it,g[u]) if (e[*it].residual()>0) {
                int v=e[*it].to;
                if (d[v]>d[u]+e[*it].cost) {
                    d[v]=d[u]+e[*it].cost;
                    tr[v]=*it;
                    if (!inq[v]) {
                        q.push(v);
                        inq[v]=true;
                    }
                }
            }
        }
        return (d[t]<INF);
    }
    ii getflow(int s,int t) {
        int totflow=0;
        int totcost=0;
        while (FordBellman(s,t)) {
            int delta=INF;
            for (int u=t;u!=s;u=e[tr[u]].from) minimize(delta,e[tr[u]].residual());
            for (int u=t;u!=s;u=e[tr[u]].from) {
                e[tr[u]].flow+=delta;
                e[tr[u]^1].flow-=delta;
            }
            totflow+=delta;
            totcost+=delta*d[t];
        }
        return (ii(totflow,totcost));
    }
};
MaxFlowMinCost g;
int n,m,s,t;
queue<int> q[MAX];
void loadgraph(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    scanf("%d",&s);
    scanf("%d",&t);
    g=MaxFlowMinCost(n+1);
    REP(i,m) {
        int u,v,c;
        scanf("%d",&u);
        scanf("%d",&v);
        scanf("%d",&c);
        g.addedge(u,v,1,c);
        g.addedge(v,u,1,c);
    }
    g.addedge(n+1,s,2,0);
}
void process(void) {
    ii res=g.getflow(n+1,t);
    if (res.fi<2) {
        printf("-1");
        return;
    }
    printf("%d\n",res.se);
    FORE(it,g.e) if (it->flow>0 && it->from<=n) q[it->from].push(it->to);
    REP(i,2) {
        vector<int> way;
        way.clear();
        int u=s;
        while (u!=t) {
            assert(!q[u].empty());
            way.push_back(u);
            int v=q[u].front();q[u].pop();
            u=v;
        }
        way.push_back(t);
        printf("%d",way.size());
        FORE(it,way) printf(" %d",*it);
        printf("\n");
    }
}
int main(void) {
    loadgraph();
    process();
    return 0;
}