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

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define fi first
#define se second
#define N 500
#define INF 1000000000
#define TR(v, it) for(typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)

int gas[N], c[N][N], n, m;
vvii g;
vvi t;

void enter() {
    scanf("%d",&n);
    for(int i = 0; i < n; ++i) scanf("%d", gas+i);
    scanf("%d",&m); g.resize(n);
    for(int i = 0; i < m; ++i) {
        int u, v, l, t; scanf("%d%d%d%d", &u, &v, &l, &t);
        --u; --v; c[u][v] = c[v][u] = t;
        g[u].push_back(ii(v, l));
        g[v].push_back(ii(u, l));
    }
}

void dijkstra() {
    t.resize(n); vi d = vi(n, INF); d[0] = 0;
    priority_queue<ii, vii, greater<ii> > qu; qu.push(ii(0, 0));
    while(!qu.empty()) {
        int du = qu.top().fi, u = qu.top().se; qu.pop();
        if(du > d[u]) continue;
        TR(g[u], it) {
            int v = it->fi, l = it->se;
            if(du + l < d[v]) {
                t[v] = vi(1, u);
                qu.push(ii(d[v] = du + l, v));
            } else if(du + l == d[v]) t[v].push_back(u);
        }
    }
}

bool bfs(int w) {
    queue<ii> qu; qu.push(ii(n-1, w));
    while(!qu.empty()) {
        int u = qu.front().fi, e = qu.front().se; qu.pop();
        if(u == 0) return 1;
        TR(t[u], it) {
            int v = *it;
            if(c[u][v] <= e) qu.push(ii(v, gas[v] ? w : e - c[u][v]));
        }
    }
    return 0;
}

void calcW() {
    int lo = 0, hi = INF;
    while(lo < hi) {
        int mid = (lo+hi)/2;
        if(bfs(mid)) hi = mid; else lo = mid + 1;
    }
    printf("%d\n", lo);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    enter();
    dijkstra();
    calcW();
    return 0;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <queue>
#include <list>
#include <map>
#include <set>
#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 <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 = 505;
const int oo = 1000000009;
using namespace std;
int d1[N], dn[N];
bool recharge[N];
int n, m, limit, len;

struct edge {
    int to, t, c;
    edge(int _v, int _t, int _c) {
        to = _v; t = _t; c = _c;
    }
};
vector<edge> a[N];

void dijkstra(int source, int d[N]) {
    priority_queue<II, vector<II>, greater<II> > Q;
    Q.push(MP(0, source));
    REP(i, 1, n) d[i] = oo;
    d[source] = 0;
    while (!Q.empty()) {
        int u = Q.top().Y, du = Q.top().X; Q.pop();
        TR(it, a[u]) {
            int v = it -> to;
            int uv = it -> t;
            if (d[v] > d[u] + uv) {
                d[v] = d[u] + uv;
                Q.push(MP(d[v], v));
            }
        }
    }
}

bool ok(int u, int d, int c) {
    if (u == n) return 1;
    if (recharge[u]) c = limit;
    TR(it, a[u]) {
        int v = it -> to;
        int tuv = it -> t;
        int cuv = it -> c;
        if (d + tuv + dn[v] == len && c >= cuv && ok(v, d + tuv, c - cuv)) return 1;
    }
    return 0;
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    REP(i, 1, n) cin >> recharge[i];
    cin >> m;
    int u, v, t, c;
    FOR(i, 0, m) {
        cin >> u >> v >> t >> c;
        a[u].PB(edge(v, t, c));
        a[v].PB(edge(u, t, c));
    }
    dijkstra(1, d1); dijkstra(n, dn);
    //REP(i, 1, n) cout << d1[i] << ' '; cout << endl;
    //REP(i, 1, n) cout << dn[i] << ' '; cout << endl;
    len = d1[n];
    int l = 0, r = 1e9, ans;
    while (l <= r) {
        int mid = l + r >> 1;
        limit = mid;
        if (ok(1, 0, mid)) {
            ans = mid; r = mid - 1;
        }
        else
            l = mid + 1;
    }
    cout << ans;
    return 0;
}

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=501;
  oo=5000001;
type
  list=^node;
  node=record
         u:longint;
         next:list;
       end;
var
  f1,f2:text;
  first,last,spt,hsize,n:longint;
  ke:array[1..MAXN] of list;
  c,t:array[1..MAXN,1..MAXN] of longint;
  queue,inq,hpos,h,a,d1,dn,e: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 add(u:longint; var a:list);
var
  p:list;
begin
  new(p); p^.u:=u;
  p^.next:=a; a:=p;
end;
procedure inp;
var
  i,m,u,v:longint;
begin
  read(f1,n);
  for i:=1 to n do read(f1,a[i]);
  read(f1,m);
  for i:=1 to m do
    begin
      read(f1,u,v,t[u,v],c[u,v]);
      t[v,u]:=t[u,v]; c[v,u]:=c[u,v];
      add(u,ke[v]);
      add(v,ke[u]);
    end;
end;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure down1(i:longint);
var
  j:longint;
begin
  j:=i<<1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (d1[h[j+1]]<d1[h[j]]) then inc(j);
      if (d1[h[j]]<d1[h[i]]) then
        begin
          swap(hpos[h[i]],hpos[h[j]]);
          swap(h[i],h[j]);
        end;
      i:=j; j:=i<<1;
    end;
end;
procedure up1(i:longint);
var
  j:longint;
begin
  j:=i>>1;
  while (i>1) and (d1[h[i]]<d1[h[j]]) do
    begin
      swap(hpos[h[i]],hpos[h[j]]);
      swap(h[i],h[j]);
      i:=j; j:=i>>1;
    end;
end;
procedure push1(u:longint);
begin
  inc(hsize); h[hsize]:=u; hpos[u]:=hsize;
  up1(hsize);
end;
procedure pop1(var u:longint);
begin
  u:=h[1]; hpos[u]:=0;
  swap(h[1],h[hsize]);
  hpos[h[1]]:=1;
  dec(hsize);
  down1(1);
end;
procedure left;
var
  u,v:longint;
  p:list;
begin
  for u:=2 to n do d1[u]:=oo;
  d1[1]:=0; hsize:=0; push1(1);
  while hsize>0 do
    begin
      pop1(u);
      p:=ke[u];
      while p<>nil do
        begin
          v:=p^.u; p:=p^.next;
          if d1[v]>d1[u]+t[u,v] then
            begin
              d1[v]:=d1[u]+t[u,v];
              if hpos[v]=0 then push1(v)
              else up1(hpos[v]);
            end;
        end;
    end;
end;
procedure down2(i:longint);
var
  j:longint;
begin
  j:=i<<1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (dn[h[j+1]]<dn[h[j]]) then inc(j);
      if (dn[h[j]]<dn[h[i]]) then
        begin
          swap(hpos[h[i]],hpos[h[j]]);
          swap(h[i],h[j]);
        end;
      i:=j; j:=i<<1;
    end;
end;
procedure up2(i:longint);
var
  j:longint;
begin
  j:=i>>1;
  while (i>1) and (dn[h[i]]<dn[h[j]]) do
    begin
      swap(hpos[h[i]],hpos[h[j]]);
      swap(h[i],h[j]);
      i:=j; j:=i>>1;
    end;
end;
procedure push2(u:longint);
begin
  inc(hsize); h[hsize]:=u; hpos[u]:=hsize;
  up2(hsize);
end;
procedure pop2(var u:longint);
begin
  u:=h[1]; hpos[u]:=0;
  swap(h[1],h[hsize]);
  hpos[h[1]]:=1;
  dec(hsize); down2(1);
end;
procedure right;
var
  v,u:longint;
  p:list;
begin
  fillchar(hpos,sizeof(hpos),0);
  for u:=1 to n-1 do dn[u]:=oo;
  dn[n]:=0;
  hsize:=0; push2(n);
  while hsize>0 do
    begin
      pop2(u);
      p:=ke[u];
      while p<>nil do
        begin
          v:=p^.u; p:=p^.next;
          if dn[v]>dn[u]+t[u,v] then
            begin
              dn[v]:=dn[u]+t[u,v];
              if hpos[v]=0 then push2(v)
              else up2(hpos[v]);
            end;
        end;
    end;
end;
function check(w:longint):boolean;
var
  u,v,x:longint;
  p:list;
begin
  fillchar(inq,sizeof(inq),0);
  for u:=1 to n do e[u]:=-1;
  first:=1; last:=1; spt:=1; queue[1]:=1; e[1]:=w; inq[1]:=1;
  while spt>0 do
    begin
      u:=queue[first]; inc(first); if first=MAXN then first:=1; dec(spt);
      inq[u]:=0;
      p:=ke[u];
      while p<>nil do
        begin
          v:=p^.u; p:=p^.next;
          if d1[u]+t[u,v]+dn[v]>d1[n] then continue;
          if e[u]<c[u,v] then continue;
          if a[v]=0 then x:=e[u]-c[u,v] else x:=w;
          if x>e[v] then
            begin
              e[v]:=x;
              if inq[v]=0 then
                begin inc(last); if last=MAXN then last:=1; queue[last]:=v; inc(spt); end;
              inq[v]:=1;
            end;
        end;
    end;
  check:=e[n]>=0;
end;
procedure solve;
var
  u,l,r,mid:longint;
begin
  l:=0; r:=oo;
  repeat
    mid:=(l+r)>>1;
    if check(mid) then r:=mid else l:=mid;
  until r-l<=1;
  if check(l) then writeln(f2,l)
  else writeln(f2,r);
end;
begin
  openF;
  inp;
  left;
  right;
  solve;
  closeF;
end.

Code mẫu của khuc_tuan

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

struct Node {
    int v, t, c;
    Node *next;
};

int n;
int mark[505];
Node * ke[505];
int F[505], G[505];
bool inq[505];

void add( Node * & p, int v, int t, int c) {
    Node * q = new Node;
    q->v = v;
    q->t = t;
    q->c = c;
    q->next = p;
    p = q;
}

int main() {
    scanf("%d", &n);
    for(int i=1;i<=n;++i) scanf("%d", mark+i);
    mark[1] = mark[n] = 1;
    int m;
    scanf("%d", &m);
    for(int i=0;i<m;++i) {
        int u, v, t, c;
        scanf("%d%d%d%d", &u, &v, &t, &c);
        add( ke[u], v, t, c);
        add( ke[v], u, t, c);
    }
    memset( F, 0x1f, sizeof(F));
    F[1] = 0;
    queue<int> q;
    q.push(1);
    inq[1] = true;
    while(!q.empty()) {
        int u = q.front();
        inq[u] = false;
        q.pop();
        for(Node *p = ke[u]; p!=NULL; p = p->next) {
            int v = p->v;
            if(F[v]>F[u]+p->t) {
                F[v] = F[u] + p->t;
                if(!inq[v]) q.push(v), inq[v] = true;
            }   
        }   
    }

    int left = 0, right = 500 * 10000;
    while(left<right) {
        int mid = (left + right) / 2;
        memset( G, -1, sizeof(G));
        G[1] = mid;
        queue<int> q;
        q.push(1);
        memset( inq, false, sizeof(inq));
        inq[1] = true;
        while(!q.empty()) {
            int u = q.front();
            inq[u] = false;
            q.pop();
            for(Node *p = ke[u]; p!=NULL; p=p->next) {
                int v = p->v;
                if(F[v] == F[u] + p->t) {
                    if(G[v]<G[u]-p->c) {
                        G[v] = G[u] - p->c;
                        if(mark[v]) G[v] = mid;
                        if(!inq[v]) q.push(v), inq[v] = true;
                    }
                }   
            }
        }   
        if(G[n]!=-1) right = mid;
        else left = mid + 1;
    }
    cout << left << endl;
    //system("pause");
    return 0;
}