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 ladpro98

#include <bits/stdc++.h>
#define ii pair<int, int>
#define iii pair<int, ii>
#define X first
#define Y second
const int N = 111;
const double eps = 1e-4;
using namespace std;
vector<iii> e;
int n, m;
double d[N];

bool Relax(iii e, double w) {
    bool ret = d[e.Y.X] + e.X - w < d[e.Y.Y];
    if (ret)
        d[e.Y.Y] = d[e.Y.X] + e.X - w;
    return ret;
}

bool NC_exist(double avg) {
    //check if there is a negative cycle using BellmanFord Alg
    //each edge is decreased by avg
    int i, j; bool stop;
    for(i = 1; i <= n; i++) d[i] = 0;
    for(i = 1; i < n; i++) {
        stop = true;
        for(j = 0; j < m; j++)
            if (Relax(e[j], avg))
                stop = false;
        if (stop) break;
    }
    for(j = 0; j < m; j++)
        if (Relax(e[j], avg)) return true;
    return false;
}

int main()
{
    //freopen("QBTRANS.in", "r", stdin);
    scanf("%d %d\n", &n, &m);
    int i, u, v, c;
    for(i=0; i<m; i++) {
        scanf("%d %d %d\n", &u, &v, &c);
        e.push_back(iii(c, ii(u, v)));
    }
    double l = 0, r = 1e9, mid, res = -1;
    while (r - l > eps) {
        mid = (l + r) / 2;
        if (NC_exist(mid)) {
            res = mid;
            r = mid;
        }
        else
            l = mid;
    }
    if (res < 0 || res > 1e8) printf("-1");
    else printf("%.2f", res);
    return 0;
}

Code mẫu của RR

//Written by Nguyen Thanh Trung
{$R-,Q-}
{$Mode objFPC}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       111;
  gh            =       10;
  eps           =       5e-3;
  oo            =       1000111000;
type
  real          =       extended;
  Tedge         =       record u,v,c:longint; end;
var
  f1,f2         :       text;
  n,m           :       longint;
  edge          :       array[1..MAXN*MAXN] of Tedge;
  d             :       array[1..MAXN] of real;
  trace         :       array[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:longint;
    begin
      read(f1,n,m);
      for i:=1 to m do
        with edge[i] do read(f1,u,v,c);
    end;
function check(val:real):boolean; inline;
    var
      found:boolean;
      i,nn:longint;
    begin
      fillchar(d,sizeof(d),0);

      for nn:=1 to gh do
        begin
          fillchar(trace,sizeof(trace),0);
          found:=false;
          for i:=1 to m do
          with edge[i] do
            if d[v]>d[u]+c-val+eps then
              begin
                trace[v]:=u;
                d[v]:=d[u]+c-val;
                found:=true;
              end;
          if not found then exit(true);
        end;
      exit(false);
    end;
function findMax:longint;
    var
      i,kq:longint;
    begin
      kq:=0;
      for i:=1 to m do
        kq:=max(kq,edge[i].c);
      exit(kq);
    end;
procedure solve;
    var
      l,r,mid,kq:real;
    begin
      kq:=-1; l:=0; r:=findMax+eps;
      while l<r do
        begin
          mid:=(l+r)/2;
          if not check(mid) then
            begin
              kq:=mid;
              r:=mid-eps;
            end
          else l:=mid+eps;
        end;
      if check(kq) then begin end;
      if kq=-1 then writeln(f2,kq:0:0)
      else writeln(f2,trunc(kq*100)/100:0:2);
    end;

begin
  openF;
  inp;
  solve;
  closeF;
end.

Code mẫu của khuc_tuan

#include <iostream>
#include <queue>
using namespace std;

int n, m;
int a[111][111];
double d[111];
bool inq[111];
int step[111];

int main() {
    scanf("%d%d", &n, &m);  
    for(int i=0;i<m;++i) {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        if(a[u][v]==0) a[u][v] = c;
        else a[u][v] <?= c;
    }
    double left = 0, right = 1e7;
    for(int kk=0;kk<40;++kk) {
        double mid = (left+right) / 2;
        queue<int> q;
        for(int i=1;i<=n;++i) d[i] = 0, q.push(i);
        memset( inq, true, sizeof(inq));
        memset( step, 0, sizeof(step));
        bool OK = false;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            inq[u] = false;
            for(int v=1;v<=n;++v) if(a[u][v] > 0 && d[v] > d[u] + a[u][v] - mid) {
                d[v] = d[u] + a[u][v] - mid;
                step[v] = step[u] + 1;
                if(step[v] >= n + 3) {
                    OK = true;  
                    goto lab;
                }
                if(!inq[v]) {
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
        lab : ;
        if(OK) right = mid;
        else left = mid;
    }
//  cout << left << " " << right << endl;
    if(left > 1e7 - 2) cout << -1 << endl;
    else printf("%.2f\n", left);
    // system("pause");
    return 0;
}