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

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

int d[N], rd[N], n, m, k, s, t;
vvii g, rg;

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

void Dijkstra(const vvii &g, int *d, const int &s) {
    fill(d, d+n, INT_MAX); d[s] = 0;
    priority_queue<ii, vii, greater<ii> > qu; qu.push(ii(0, s));
    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]) qu.push(ii(d[v] = du + l, v));
        }
    }
}

void solve() {
    Dijkstra(g, d, s); Dijkstra(rg, rd, t);
    /*for(int i = 0; i < n; ++i) printf("%d ", d[i]); putchar(10);
    for(int i = 0; i < n; ++i) printf("%d ", rd[i]); putchar(10);*/
    int res = d[t];
    for(int i = 0; i < k; ++i) {
        int u, v, l; scanf("%d%d%d", &u, &v, &l); --u; --v;
        if(d[u] != INT_MAX && rd[v] != INT_MAX)
            res = min(res, d[u] + rd[v] + l);
        if(d[v] != INT_MAX && rd[u] != INT_MAX)
            res = min(res, d[v] + rd[u] + l);
        //res = min(res, min(d[u] + rd[v] + l, d[v] + rd[u] + l));
    }
    printf("%d\n", res == INT_MAX ? -1 : res);
}

int main() {
#ifdef __DONGOCKHANH__
    freopen("input.txt", "r", stdin);
#endif
    int tc; scanf("%d", &tc);
    while(tc--) {
        enter();
        solve();
    }
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
#define ii pair<int, int>
const int N = 10005;
const int oo = 1000000009;
using namespace std;
vector<ii> a[2][N];
int d[2][N], m, n, s, tt, k, t;

void Dijkstra(int source, int p) {
    priority_queue<ii, vector<ii>, greater<ii> > Q;
    Q.push(ii(0, source));
    int i, v, uv, u, du;
    ii t;
    for(i=1; i<=n; i++) d[p][i] = oo;
    d[p][source] = 0;
    while (Q.size()) {
        t = Q.top(); Q.pop();
        u = t.second; du = t.first;
        if (du != d[p][u]) continue;
        for(i=0; i<a[p][u].size(); i++) {
            v = a[p][u][i].first;
            uv = a[p][u][i].second;
            if (d[p][v] > d[p][u] + uv) {
                d[p][v] = d[p][u] + uv;
                Q.push(ii(d[p][v], v));
            }
        }
    }
}

int main()
{
    //freopen("TRAFFICN.in", "r", stdin);
    scanf("%d\n", &tt);
    int i, u, v, c, res;
    while (tt--) {
        scanf("%d %d %d %d %d\n", &n, &m, &k, &s, &t);
        for(i=1; i<=n; i++) {a[0][i].clear();a[1][i].clear();}
        for(i=1; i<=m; i++) {
            scanf("%d %d %d\n", &u, &v, &c);
            a[0][u].push_back(ii(v, c));
            a[1][v].push_back(ii(u, c));
        }
        Dijkstra(s, 0);
        Dijkstra(t, 1);
        res = d[0][t];
        while (k--) {
            scanf("%d %d %d\n", &u, &v, &c);
            res = min(res, min(d[0][u] + c + d[1][v], d[0][v] + c+ d[1][u]));
        }
        if (res == oo) res = -1;
        printf("%d\n", res);
    }
    return 0;
}

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=10111;
  oo=1000000011;
type
  list=^node;
  node=record
         u,c:longint;
         next:list;
       end;
var
  f1,f2:text;
  hsize,ntest,test,n,m,s,t,k:longint;
  ec,eu,ev:array[1..350] of longint;
  h,hpos:array[1..MAXN] of longint;
  d:array[0..1,1..MAXN] of longint;
  ke,ke2:array[1..MAXN] of list;
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,c:longint; var a:list);
var
  p:list;
begin
  new(p); p^.u:=u; p^.c:=c;
  p^.next:=a; a:=p;
end;
procedure inp;
var
  i,u,v,c:longint;
begin
  read(f1,n,m,k,s,t);
  fillchar(ke,sizeof(ke),0);
  fillchar(ke2,sizeof(ke2),0);
  for i:=1 to m do
    begin
      read(f1,u,v,c);
      add(v,c,ke[u]);
      add(u,c,ke2[v]);
    end;
  for i:=1 to k do
    read(f1,eu[i],ev[i],ec[i]);
end;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure downHeap(cs,i:longint);
var
  j:longint;
begin
  j:=i<<1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (d[cs,h[j+1]]<d[cs,h[j]]) then inc(j);
      if (d[cs,h[j]]<d[cs,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 upHeap(cs,i:longint);
var
  j:longint;
begin
  j:=i>>1;
  while (i>1) and (d[cs,h[i]]<d[cs,h[j]]) do
    begin
      swap(hpos[h[i]],hpos[h[j]]);
      swap(h[i],h[j]);
      i:=j; j:=i>>1;
    end;
end;
procedure push(cs,u:longint);
begin
  inc(hsize); h[hsize]:=u; hpos[u]:=hsize;
  upHeap(cs,hsize);
end;
procedure pop(cs:longint; var u:longint);
begin
  u:=h[1]; hpos[u]:=0;
  swap(h[1],h[hsize]); hpos[h[1]]:=1;
  dec(hsize); downHeap(cs,1);
end;
procedure solve;
var
  u,v,c,i,kq:longint;
  p:list;
begin
  for u:=1 to n do d[0,u]:=oo;
  d[0,s]:=0;
  fillchar(hpos,sizeof(hpos),0); hsize:=0;
  push(0,s);
  while hsize>0 do
    begin
      pop(0,u);
      p:=ke[u];
      while p<>nil do
        begin
          v:=p^.u; c:=p^.c; p:=p^.next;
          if d[0,v]>d[0,u]+c then
            begin
              d[0,v]:=d[0,u]+c;
              if hpos[v]=0 then push(0,v)
              else upHeap(0,hpos[v]);
            end;
        end;
    end;
  for u:=1 to n do d[1,u]:=oo;
  d[1,t]:=0;
  fillchar(hpos,sizeof(hpos),0); hsize:=0;
  push(1,t);
  while hsize>0 do
    begin
      pop(1,u);
      p:=ke2[u];
      while p<>nil do
        begin
          v:=p^.u; c:=p^.c; p:=p^.next;
          if d[1,v]>d[1,u]+c then
            begin
              d[1,v]:=d[1,u]+c;
              if hpos[v]=0 then push(1,v)
              else upHeap(1,hpos[v]);
            end;
        end;
    end;
  kq:=min(d[0,t],d[1,s]);
  for i:=1 to k do
    begin
      u:=eu[i]; v:=ev[i]; c:=ec[i];
      kq:=min(kq,d[0,u]+d[1,v]+c);
      kq:=min(kq,d[0,v]+d[1,u]+c);
    end;
  if kq=oo then writeln(f2,-1)
  else writeln(f2,kq);
end;
begin
  openF;
  read(f1,ntest);
  for test:=1 to ntest do
    begin
      inp;
      solve;
    end;
  closeF;
end.

Code mẫu của hieult

#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.000000001
#define maxn 10011
#define oo 1111111111
#define modunlo 111539786
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
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;

struct canh{
     int id,gt;
     canh(){};
     canh(int _id, int _gt){
          id = _id;
          gt = _gt; 
     }
};

struct doan{
     int chiso,gt;
     doan(){};
     doan(int _chiso,int _gt){
          chiso = _chiso;
          gt = _gt; 
     }
     bool operator <(const doan D)const{
          return gt<D.gt;
     }  
};

set<doan> S1,S2;
set<doan>::iterator it;
int f1[111111],f2[111111];
vector<vector<canh> > V1,V2;
int n,m,k,s,t,test;
int x,y,c,u,v,uu,vv;

int main(){

    // freopen("TRAFFICN.in","r",stdin);

     scanf("%d",&test);
     for(int itest = 1;itest<=test;itest++){

     scanf("%d %d %d %d %d",&n,&m,&k,&s,&t);
     V1.clear(); V2.clear();
     V1.resize(n+3); V2.resize(n+3);
     memset(f1,-1,sizeof(f1));
     memset(f2,-1,sizeof(f2));

     for(int i = 0;i<m;i++){
          scanf("%d %d %d",&x,&y,&c);
          V1[x].push_back(canh(y,c));
          V2[y].push_back(canh(x,c));
     }

     S1.clear();  
     S1.insert(doan(s,0));
     while(S1.size()){
          it = S1.begin();
          u = (*it).chiso;
          v = (*it).gt;
          S1.erase(S1.begin());
          if(f1[u]==-1){
               f1[u] = v;
               TR(V1[u],it){
                    uu = (*it).id;
                    vv = (*it).gt;
                    if(f1[uu]==-1){
                         S1.insert(doan(uu,v+vv));
                    }
               }
          }
     }     

     S2.clear();
     S2.insert(doan(t,0));
     while(S2.size()){
           it = S2.begin();
           u = (*it).chiso;
           v = (*it).gt;
           S2.erase(S2.begin());
           if(f2[u]==-1){
                f2[u] = v;
                TR(V2[u],it){
                     uu = (*it).id;
                     vv = (*it).gt;
                     if(f2[uu]==-1) S2.insert(doan(uu,v+vv));
                }
           }
     }

    // for(int i = 1;i<=n;i++) printf("%d %d\n",f1[i],f2[i]);

     int kq = oo;
     if(f1[t]!=-1) kq = f1[t];
     for(int i = 0;i<k;i++){
           scanf("%d %d %d",&x,&y,&c);
           if(f1[x]!=-1 && f2[y]!=-1) kq = min(kq,f1[x]+f2[y]+c);
           if(f1[y]!=-1 && f2[x]!=-1) kq = min(kq,f1[y]+f2[x]+c);
     }

     if(kq<oo) printf("%d\n",kq);
     else printf("-1\n");

     }
    // getch();
}

Code mẫu của ll931110

Program TRAFFICN;
        Const
                input  = '';
                output = '';
                  maxn = 10000;
                  maxm = 100000;
                  maxv = 1000000000;
        Type
                arrn = array[1..maxn + 1] of longint;
                arrm = array[1..maxm + 1] of longint;
        Var
             h,hs,ht,heap,pos: arrn;
                      d,ds,dt: arrn;
                  adj,adjcost: arrm;
                adjs,adjcosts: arrm;
                adjt,adjcostt: arrm;
                        x,y,c: arrm;
                         free: array[1..maxn] of boolean;
                    n,m,k,s,t: longint;
                       test,i: integer;
                        nHeap: longint;
                        fi,fo: text;

Procedure openfile;
          Begin
                Assign(fi, input);
                        Reset(fi);

                Assign(fo, output);
                        Rewrite(fo);
          End;

Procedure LoadGraph;
          Var
                i: longint;
          Begin
                Fillchar(hs, sizeof(hs), 0);
                Fillchar(ht, sizeof(ht), 0);

                Readln(fi, n, m, k, s, t);
                For i:= 1 to m do
                        Begin
                                Readln(fi, x[i], y[i], c[i]);
                                inc(hs[x[i]]);
                                inc(ht[y[i]]);
                        End;

                For i:= 2 to n do hs[i]:= hs[i] + hs[i - 1];
                For i:= 2 to n do ht[i]:= ht[i] + ht[i - 1];

                For i:= 1 to m do
                        Begin
                                adjs[hs[x[i]]]:= y[i];
                                adjcosts[hs[x[i]]]:= c[i];
                                dec(hs[x[i]]);

                                adjt[ht[y[i]]]:= x[i];
                                adjcostt[ht[y[i]]]:= c[i];
                                dec(ht[y[i]]);
                        End;

                hs[n + 1]:= m;
                ht[n + 1]:= m;
          End;

Procedure update(v: longint);
          Var
                parent,child: longint;
          Begin
                child:= pos[v];
                If child = 0 then
                        Begin
                                inc(nHeap);
                                child:= nHeap;
                        End;

                parent:= child div 2;
                While (parent > 0) and (d[heap[parent]] > d[v]) do
                        Begin
                                heap[child]:= heap[parent];
                                pos[heap[child]]:= child;

                                child:= parent;
                                parent:= child div 2;
                        End;

                heap[child]:= v;
                pos[v]:= child;
          End;

Function pop: longint;
         Var
                r,c,v: longint;
         Begin
                pop:= heap[1];
                v:= heap[nHeap];
                dec(nHeap);

                r:= 1;
                While r * 2 <= nHeap do
                  Begin
                        c:= r * 2;
                        If (c <= nHeap) and (d[heap[c + 1]] < d[heap[c]]) then inc(c);

                        If d[v] <= d[heap[c]] then break;
                        heap[r]:= heap[c];
                        pos[heap[r]]:= r;
                        r:= c;
                  End;

                heap[r]:= v;
                pos[v]:= r;
         End;

Procedure Dijkstra(s: longint);
          Var
                u,v,i,iv: longint;
          Begin
                nHeap:= 0;

                Fillchar(pos, sizeof(pos), 0);
                Fillchar(free, sizeof(free), true);

                For i:= 1 to n do d[i]:= maxv;
                d[s]:= 0;

                update(s);
                Repeat
                        u:= pop;
                        free[u]:= false;

                        For iv:= h[u] + 1 to h[u + 1] do
                          Begin
                                v:= adj[iv];
                                If free[v] and (d[v] > d[u] + adjcost[iv]) then
                                        Begin
                                                d[v]:= d[u] + adjcost[iv];
                                                update(v);
                                        End;
                          End;
                Until nHeap = 0;
          End;

Procedure solve;
          Var
                i,minway: longint;
                u,v,cost: longint;
                     tmp: longint;
          Begin
                h:= hs;
                adj:= adjs;
                adjcost:= adjcosts;
                Dijkstra(s);
                ds:= d;

                h:= ht;
                adj:= adjt;
                adjcost:= adjcostt;
                Dijkstra(t);
                dt:= d;

                minway:= ds[t];
                For i:= 1 to k do
                  Begin
                        Readln(fi, u, v, cost);

                        tmp:= ds[u] + dt[v] + cost;
                        If minway > tmp then minway:= tmp;

                        tmp:= ds[v] + dt[u] + cost;
                        If minway > tmp then minway:= tmp;
                  End;

                If minway = maxv then writeln(fo, -1)
                                 else writeln(fo, minway);
          End;

Procedure closefile;
          Begin
                Close(fo);
                Close(fi);
          End;

Begin
        openfile;

        Readln(fi, test);
        For i:= 1 to test do
                Begin
                        LoadGraph;
                        solve;
                End;

        closefile;
End.

Code mẫu của skyvn97

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define MAX   10010
#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;
typedef pair<int,int> ii;
const int INF=(int)1e9+7;
vector<ii> gf[MAX],gb[MAX],ga[MAX];
int d[3][MAX];
int m,n,k,s,t;
void minimize(int &x,const int &y) {
    if (x>y) x=y;
}
void loadgraph(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    scanf("%d",&k);
    scanf("%d",&s);
    scanf("%d",&t);
    FOR(i,1,n) {
        gf[i].clear();
        gb[i].clear();
        ga[i].clear();
    }
    REP(i,m) {
        int u,v,w;
        scanf("%d",&u);
        scanf("%d",&v);
        scanf("%d",&w);
        gf[u].push_back(ii(v,w));
        gb[v].push_back(ii(u,w));
    }
    REP(i,k) {
        int u,v,w;
        scanf("%d",&u);
        scanf("%d",&v);
        scanf("%d",&w);
        ga[u].push_back(ii(v,w));
        ga[v].push_back(ii(u,w));
    }
    memset(d,0x3f,sizeof d);
}
void dijkstra(int s,vector<ii> g[],int d[]) {
    priority_queue<ii,vector<ii>,greater<ii> > q;
    while (!q.empty()) q.pop();
    d[s]=0;
    q.push(ii(0,s));
    while (!q.empty()) {
        int u=q.top().se;
        int w=q.top().fi;
        q.pop();
        FORE(it,g[u]) if (w+it->se<d[it->fi]) {
            d[it->fi]=w+it->se;
            q.push(ii(d[it->fi],it->fi));
        }
    }
}
void process(void) {    
    dijkstra(s,gf,d[0]);
    dijkstra(t,gb,d[1]);
    int res=d[0][t];
    FOR(i,1,n) FORE(j,ga[i]) minimize(res,d[0][i]+j->se+d[1][j->fi]);
    if (res>=INF) printf("-1\n"); else printf("%d\n",res);
}
int main(void) {
#ifndef ONLINE_JUDGE
    freopen("tmp.txt","r",stdin);
#endif
    int tc;
    scanf("%d",&tc);
    REP(ct,tc) {
        loadgraph();
        process();  
    }
    return 0;
}

Code mẫu của khuc_tuan

// {$APPTYPE CONSOLE}
 {$mode delphi}

uses math, sysutils;

type
    PData = ^Data;
    Data = record
        v, c : integer;
        n : PData;
    end;

    ArrData = array[1..10000] of PData;
    ArrInt = array[1..10000] of integer;

procedure Add( var d : PData; v, c : integer);
var
    p : PData;
begin
    new(p);
    p.v := v;
    p.c := c;
    p.n := d;
    d := p;
end;

var
    m, n : integer;
    s, t : integer;
    ke, ken : ArrData;
    ds, dt : ArrInt;
    h, pos : ArrInt;
    nh : integer;

procedure pushdown(i : integer; var d : ArrInt);
var
    j, t : integer;
begin
    while 2*i <= nh do
    begin
        j := 2 * i;
        if (j<nh) and (d[h[j+1]] < d[h[j]]) then inc(j);
        if d[h[j]] < d[h[i]] then
        begin
            t := h[i]; h[i] := h[j]; h[j] := t;
            pos[h[i]] := i;
            pos[h[j]] := j;
            i := j;
        end
        else break;
    end;
end;

procedure pushup(i : integer; var d : ArrInt);
var
    j, t : integer;
begin
    while i >= 2 do
    begin
        j := i div 2;
        if d[h[j]] > d[h[i]] then
        begin
            t := h[i]; h[i] := h[j]; h[j] := t;
            pos[h[i]] := i;
            pos[h[j]] := j;
            i := j;
        end
        else break;
    end;
end;

procedure addheap(i : integer; var d : ArrInt);
begin
    inc(nh);
    h[nh] := i;
    pos[i] := nh;
    pushup(nh, d);
end;

function extractmin(var d : ArrInt) : integer;
begin
    extractmin := h[1];
    h[1] := h[nh];
    dec(nh);
    pos[h[1]] := 1;
    pushdown(1, d);
end;

procedure dijkstra(var ke : ArrData; s : integer; var d : ArrInt);
var
    k, u, v, i : integer;
    p : PData;
begin
    for i:=1 to n do
        d[i] := 1000000000;
    fillchar( pos, sizeof(pos), -1);
    d[s] := 0;
    nh := 0;
    addheap(s, d);
    while nh > 0 do
    begin
        u := extractmin(d);
        p := ke[u];
        while p<>nil do
        begin
            v := p.v;
            if d[v] > d[u] + p.c then
            begin
                d[v] := d[u] + p.c;
                if pos[v]=-1 then addheap( v, d)
                else
                begin
                    k := pos[v];
                    pushup(k, d);
                end;
            end;
            p := p.n;
        end;
    end;
end;

var
    k, j, u, v, c, st, kk : integer;
    res : integer;
begin
    read(st);
    for kk:=1 to st do
    begin
        read(n, m, k, s, t);
        for j:=1 to n do
        begin
            ke[j] := nil;
            ken[j] := nil;
        end;
        for j:=1 to m do
        begin
            read(u,v,c);
            Add(ke[u], v, c);
            Add(ken[v], u, c);
        end;
        dijkstra(ke, s, ds);
        dijkstra(ken, t, dt);
        res := ds[t];
        for j:=1 to k do
        begin
            read(u,v,c);
            res := min( res, ds[u] + dt[v] + c);
            res := min( res, ds[v] + dt[u] + c);
        end;
        if res = 1000000000 then writeln(-1)
        else writeln(res);
    end;
end.