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=5005;
      maxc=2000000000;
var n,m:longint;
    a,w:array[1..40000] of integer;
    d,s,cur,pos:array[1..maxn] of longint;
    sl:array[1..maxn] of qword;
    free:array[1..maxn] of boolean;
    b:array[1..20000,0..3] of longint;


procedure rf;
var i,j,x,y,z,t:longint;
begin
     read(n,m);
     for i:=1 to m do
     begin
          for j:=0 to 3 do
              read(b[i,j]);
          inc(s[b[i,1]]);
          if b[i,0]=2 then inc(s[b[i,2]]);
     end;
     pos[1]:=1; cur[1]:=1;
     for i:=2 to n+1 do
     begin
          pos[i]:=pos[i-1]+s[i-1];
          cur[i]:=pos[i];
     end;
     for i:=1 to m do
     begin
          a[cur[b[i,1]]]:=b[i,2];
          w[cur[b[i,1]]]:=b[i,3];
          inc(cur[b[i,1]]);
          if b[i,0]=2 then
          begin
               a[cur[b[i,2]]]:=b[i,1];
               w[cur[b[i,2]]]:=b[i,3];
               inc(cur[b[i,2]]);
          end;
     end;
end;

procedure pr;
var i,x,t,min:longint;
begin
     for i:=1 to n do
     begin
          free[i]:=true;
          d[i]:=maxc;
     end;
     d[1]:=0; free[1]:=false; x:=1; sl[1]:=1;
     repeat
           for i:=pos[x] to pos[x+1]-1 do
             if free[a[i]] then
             begin
               if d[a[i]]=d[x]+w[i] then sl[a[i]]:=sl[a[i]]+sl[x]
               else
               begin
                    if d[a[i]]>d[x]+w[i] then
                    begin
                         d[a[i]]:=d[x]+w[i];
                         sl[a[i]]:=sl[x];
                    end;
               end;
             end;
           min:=maxc-1; t:=0;
           for i:=1 to n do
               if free[i] and (d[i]<min) then
               begin
                    min:=d[i];
                    t:=i;
               end;
           if t=0 then exit;
           x:=t; free[x]:=false;
     until not free[n];
end;

procedure wf;
begin
     writeln(d[n],' ',sl[n]);
end;

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

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#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 sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 30005
typedef long long LL;

int d[N], n, m;
LL c[N];
vvii g;

void dijkstra(vvii&g, int s, int *d, LL *c) {
    fill(d,d+n,INF); d[s] = 0; c[s] = 1;
    priority_queue< ii, vii, greater<ii> > qu;
    qu.push(ii(0,s));
    while(!qu.empty()) {
        int u = qu.top().se, du = qu.top().fi; 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));
                c[v] = c[u];
            } else if( du + l == d[v] ) c[v] += c[u];
        }
    }
}

int main() {
    scanf("%d%d",&n,&m); g.resize(n);
    rep(i,m) {
        int k, u, v, l; scanf("%d%d%d%d",&k,&u,&v,&l);
        g[--u].pb(ii(--v,l));
        if(k == 2) g[v].pb(ii(u,l));
    }
    dijkstra(g, 0, d, c);
    printf("%d %lld\n", d[n-1], c[n-1]);
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 5050;
const int INF = 1e9;

struct Edge {
    int to, cost;
    Edge(int to, int cost): to(to), cost(cost) {}
};

namespace PriorityQueue {
    static const int LIMIT = 2e5;
    vector<int> V[LIMIT];
    int size;
    int cur;

    void push(int u, int d) { V[d].push_back(u); ++size; }
    void getMin(int &u, int &du) {
        while (cur < LIMIT && V[cur].empty()) ++cur;
        assert(cur < LIMIT);
        --size;
        u = V[cur].back(); du = cur;
        V[cur].pop_back();
    }
}

int d[N];
long long cnt[N];;
int n, m;

vector<Edge> a[N];

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int k, u, v, L;
        cin >> k >> u >> v >> L;
        a[u].push_back(Edge(v, L));
        if (k == 2) a[v].push_back(Edge(u, L));
    }
    for (int i = 2; i <= n; ++i) d[i] = INF;
    PriorityQueue::push(1, 0); cnt[1] = 1;
    while (PriorityQueue::size) {
        int u, du;
        PriorityQueue::getMin(u, du);
        if (d[u] != du) continue;
        for (auto e : a[u]) {
            int v = e.to;
            int c = e.cost;
            if (d[v] > d[u] + c) {
                d[v] = d[u] + c;
                PriorityQueue::push(v, d[v]);
                cnt[v] = cnt[u];
            } else if (d[v] == d[u] + c) {
                cnt[v] += cnt[u];
            }
        }
    }
    cout << d[n] << ' ' << cnt[n] << endl;
    return 0;
}

Code mẫu của RR

{$R-,Q-}
const
  FINP='';
  FOUT='';
  MAXN=20000;
  oo=1000000000;
type
  list=^node;
  node=record u,c:longint; next:list; end;
var
  thuan,nghich:array[1..MAXN] of list;
  d,hpos,h:array[1..MAXN] of longint;
  sl:array[1..MAXN] of int64;
  hsize,n:longint;
procedure add(u,c:longint;var a:list); inline;
var
  p:list;
begin
  new(p); p^.u:=u; p^.c:=c; p^.next:=a; a:=p;
end;
procedure inp; inline;
var
  f:text;
  i,m,u,c,v,l:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n,m);
  for i:=1 to n do
    begin
      thuan[i]:=nil;
      nghich[i]:=nil;
    end;
  for i:=1 to m do
    begin
      read(f,l,u,v,c);
      add(v,c,thuan[u]);
      add(u,c,nghich[v]);
      if l=2 then
        begin
          add(u,c,thuan[v]);
          add(v,c,nghich[u]);
        end;
    end;
  close(f);
end;
procedure swap(var a,b:longint); inline;
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure downHeap(i:longint); inline;
var
  j:longint;
begin
  j:=i shl 1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (d[h[j+1]]<d[h[j]]) then inc(j);
      if d[h[j]]<d[h[i]] then
        begin
          swap(hpos[h[i]],hpos[h[j]]);
          swap(h[i],h[j]);
        end;
      i:=j; j:=i shl 1;
    end;
end;
procedure upHeap(i:longint); inline;
var
  j:longint;
begin
  j:=i shr 1;
  while (i>1) and (d[h[i]]<d[h[j]]) do
    begin
      swap(hpos[h[i]],hpos[h[j]]);
      swap(h[i],h[j]);
      i:=j; j:=i shr 1;
    end;
end;
procedure push(u:longint); inline;
begin
  inc(hsize); h[hsize]:=u; hpos[u]:=hsize;
  upHeap(hsize);
end;
procedure pop(var u:longint); inline;
begin
  u:=h[1]; hpos[u]:=0;
  swap(h[1],h[hsize]);
  hpos[h[1]]:=1; dec(hsize);
  downHeap(1);
end;
procedure dijkstra; inline;
var
  u,v,c:longint;
  p:list;
begin
  for u:=1 to n do d[u]:=oo;
  for u:=1 to n do sl[u]:=-1; sl[1]:=1;
  hsize:=0;
  d[1]:=0; push(1);
  while hsize>0 do
    begin
      pop(u);
      p:=thuan[u];
      while p<>nil do
        begin
          v:=p^.u; c:=p^.c;
          p:=p^.next;
          if d[v]>d[u]+c then
            begin
              d[v]:=d[u]+c;
              if hpos[v]=0 then push(v)
              else upHeap(hpos[v]);
            end;
        end;
    end;
end;
procedure dfs(u:longint); inline;
var
  p:list;
  v,c:longint;
begin
  if sl[u]<>-1 then exit;
  sl[u]:=0;
  p:=nghich[u];
  while p<>nil do
    begin
      v:=p^.u; c:=p^.c;
      p:=p^.next;
      if d[v]+c=d[u] then
        begin
          dfs(v);
          sl[u]:=sl[u]+sl[v];
        end;
    end;
end;
procedure ans; inline;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,d[n],' ',sl[n]);
  close(f);
end;
begin
  inp;
  dijkstra;
  dfs(n);
  ans;
end.

Code mẫu của ll931110

Program QBSCHOOL2;
        Const
                input  = '';
                output = '';
                   max = 200000000;
        Var
                       u,v,c: array[1..20000] of integer;
                           k: array[1..20000] of byte;
                           d: array[1..5000] of longint;
               adj,adjcost,h: array[1..40000] of longint;
                      numway: array[1..5000] of int64;
                        free: array[1..5000] of boolean;
                         n,m: integer;

Procedure LoadGraph;
          Var
                  f: text;
                i,t: longint;
          Begin
                Assign(f, input);
                        Reset(f);

                Fillchar(h, sizeof(h), 0);

                Readln(f, n, m);
                For i:= 1 to m do
                        Begin
                                Readln(f, k[i], u[i], v[i], c[i]);

                                inc(h[u[i]]);
                                If k[i] = 2 then inc(h[v[i]]);
                        End;

                Close(f);

                For i:= 2 to n do h[i]:= h[i] + h[i - 1];
                t:= h[n];

                For i:= 1 to m do
                    Begin
                        adj[h[u[i]]]:= v[i];
                        adjcost[h[u[i]]]:= c[i];
                        dec(h[u[i]]);

                        If k[i] = 2 then
                                Begin
                                        adj[h[v[i]]]:= u[i];
                                        adjcost[h[v[i]]]:= c[i];
                                        dec(h[v[i]]);
                                End;
                    End;

                h[n + 1]:= t;
          End;

Procedure init;
          Var
                i: longint;
          Begin
                Fillchar(free, sizeof(free), true);

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

                Fillchar(numway, sizeof(numway), 0);
                numway[1]:= 1;
          End;

Procedure Dijkstra;
          Var
                i,u,v,min,iv: longint;
          Begin
                Repeat
                        u:= 0;
                        min:= max;

                        For i:= 1 to n do
                                if free[i] and (d[i] < min) then
                                        Begin
                                                u:= i;
                                                min:= d[i];
                                        End;

                        If u = 0 then break;

                        free[u]:= false;
                        For iv:= h[u] + 1 to h[u + 1] do
                            Begin
                                v:= adj[iv];
                                If free[v] then
                                   if d[v] > d[u] + adjcost[iv] then
                                        Begin
                                                d[v]:= d[u] + adjcost[iv];
                                                numway[v]:= numway[u];
                                        End
                                else if d[v] = d[u] + adjcost[iv] then
                                        numway[v]:= numway[v] + numway[u];
                            End;
                Until false;
          End;

Procedure solve;
          Var
                f: text;
          Begin
                Assign(f, output);
                        Rewrite(f);
                        Writeln(f, d[n], ' ', numway[n]);
                Close(f);
          End;

Begin
        LoadGraph;
        init;
        Dijkstra;
        solve;
End.

Code mẫu của skyvn97

#include<stdio.h>
#include<vector>
#include<queue>
#define MAX   5555
const int INF=1e9;
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
int m,n;
vii g[MAX];
ll c[MAX];
int d[MAX];
int s,e;
void loadgraph(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    int i,k,u,v,w;
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&k);
        scanf("%d",&u);
        scanf("%d",&v);
        scanf("%d",&w);
        g[u].push_back(ii(v,w));
        if (k==2) g[v].push_back(ii(u,w));
    }
    for (i=1;i<=n;i=i+1) {
        d[i]=INF;
        c[i]=0;
    }
    c[1]=1;
    d[1]=0;
}
void dijkstra(void) {
    int i,v,w;
    ii x;
    priority_queue<ii,vii,greater<ii> > q;
    q.push(ii(0,1));
    while (!q.empty()) {
        x=q.top(); q.pop();
        w=x.first;
        v=x.second;
        for (i=0;i<g[v].size();i=i+1) {
            if (d[g[v][i].first]==w+g[v][i].second) {
                c[g[v][i].first]+=c[v];
                continue;
            }
            if (d[g[v][i].first]>w+g[v][i].second) {
                d[g[v][i].first]=w+g[v][i].second;
                c[g[v][i].first]=c[v];
                q.push(ii(d[g[v][i].first],g[v][i].first));
                continue;
            }
        }
    }
    printf("%d %lld",d[n],c[n]);
}
int main(void) {
    loadgraph();
    dijkstra();
}