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 <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 d1[N], d2[N], n, m;
LL c1[N], c2[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() {
#ifndef ONLINE_JUDGE
    freopen( "input.txt", "r", stdin );
    //freopen( "output.txt", "w", stdout );
#endif
    scanf("%d%d",&n,&m); g.resize(n);
    rep(i,m) {
        int u, v, l; scanf("%d%d%d",&u,&v,&l);
        g[--u].pb(ii(--v,l)); g[v].pb(ii(u,l));
    }
    dijkstra(g, 0, d1, c1);
    dijkstra(g, n-1, d2, c2);
    vi res;
    rep(i,n)
        if(!(d1[i]+d2[i]==d1[n-1] && c1[i]*c2[i]==c1[n-1])) res.pb(i+1);
    printf("%d\n",sz(res));
    tr(res,it) printf("%d\n",*it);
    return 0;
}

Code mẫu của ladpro98

{$MODE OBJFPC}
program centre28;
uses    math;
type    e=record
        v,w,link:longint;
        end;
const   maxn=30003;
        maxm=200005;
        oo=trunc(1e9);
        fi='';
var     adj:array[1..maxm] of e;
        head,pos,h:array[1..maxn] of longint;
        d,way:array[1..2,1..maxn] of longint;
        n,m,mm,nh:longint;

procedure input;
var     inp:text;
        i,x,y,w:longint;
begin
        assign(inp,fi);reset(inp);
        readln(inp,n,mm);
        for i:=1 to mm do
        begin
                readln(inp,x,y,w);
                inc(m);
                adj[m].v:=y;
                adj[m].w:=w;
                adj[m].link:=head[x];
                head[x]:=m;
                inc(m);
                adj[m].v:=x;
                adj[m].w:=w;
                adj[m].link:=head[y];
                head[y]:=m;
        end;
        close(inp);
end;

procedure update(dir,u:longint);
var     c,p:longint;
begin
        c:=pos[u];
        if c=0 then
        begin
                inc(nh);
                c:=nh;
        end;
        repeat
                p:=c shr 1;
                if (p=0) or (d[dir,h[p]]<=d[dir,u]) then break;
                h[c]:=h[p];
                pos[h[c]]:=c;
                c:=p;
        until false;
        h[c]:=u;
        pos[u]:=c;
end;

function extract(dir:longint):longint;
var     v,p,c:longint;
begin
        result:=h[1];
        v:=h[nh];
        dec(nh);
        p:=1;
        repeat
                c:=p shl 1;
                if (c<nh) and (d[dir,h[c+1]]<d[dir,h[c]]) then inc(c);
                if (c>nh) or (d[dir,h[c]]>=d[dir,v]) then break;
                h[p]:=h[c];
                pos[h[p]]:=p;
                p:=c;
        until false;
        h[p]:=v;
        pos[v]:=p;
end;


procedure dijkstra(source,dir:longint);
var     u,i:longint;
        v:e;
begin
        for i:=1 to n do d[dir,i]:=oo;
        for i:=1 to n do pos[i]:=0;
        d[dir,source]:=0;
        way[dir,source]:=1;
        nh:=0;
        update(dir,source);
        repeat
                u:=extract(dir);
                i:=head[u];
                while i>0 do
                begin
                        v:=adj[i];
                        if d[dir,v.v]>d[dir,u]+v.w then
                        begin
                                d[dir,v.v]:=d[dir,u]+v.w;
                                update(dir,v.v);
                                way[dir,v.v]:=way[dir,u];
                        end
                        else
                        if d[dir,v.v]=d[dir,u]+v.w then
                                inc(way[dir,v.v],way[dir,u]);
                        i:=v.link;
                end;
        until nh=0;
end;

procedure process;
var     i,res:longint;
        ver:array[1..maxn] of longint;
begin
        res:=0;
        for i:=2 to n-1 do
        if (d[1,i]+d[2,i]>d[1,n])
        or ((d[1,i]+d[2,i]=d[1,n]) and (way[1,i]*way[2,i]<way[1,n])) then
        begin
                inc(res);
                ver[res]:=i;
        end;
        writeln(res);
        for i:=1 to res do
        writeln(ver[i]);
end;

begin
        input;
        dijkstra(1,1);
        dijkstra(n,2);
        process;
end.

Code mẫu của RR

{$R+,Q+}
const
  FINP='';
  FOUT='';
  MAXN=30000;
  oo=1000000000;
type
  list=^node;
  node=record u,c:longint; next:list; end;
  mang=array[1..MAXN] of int64;
var
  p:list;
  ke:array[1..MAXN] of list;
  hsize,n:longint;
  d,h,hpos:array[1..MAXN] of longint;
  f,g:mang;
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
  f:text;
  i,m,u,v,c:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n,m);
  for i:=1 to n do ke[i]:=nil;
  for i:=1 to m do
    begin
      read(f,u,v,c);
      if u=v then continue;
      add(v,c,ke[u]);
      add(u,c,ke[v]);
    end;
  close(f);
end;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure downHeap(i:longint);
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);
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);
begin
  inc(hsize); h[hsize]:=u; hpos[u]:=hsize;
  upHeap(hsize);
end;
procedure pop(var u:longint);
begin
  u:=h[1]; hpos[u]:=0;
  swap(h[1],h[hsize]);
  hpos[h[1]]:=1; dec(hsize);
  downHeap(1);
end;
procedure dijkstra;
var
  u,v,c:longint;
  p:list;
begin
  while hsize>0 do
    begin
      pop(u);
      p:=ke[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 ans;
var
  fo:text;
  count,i:longint;
begin
  assign(fo,FOUT); rewrite(fo);
  count:=0;
  for i:=2 to n-1 do
    if (f[i]*g[i]<>f[n]) or (f[i]=-1) or (g[i]=-1) then inc(count);
  writeln(fo,count);
  for i:=2 to n-1 do
    if (f[i]*g[i]<>f[n]) or (f[i]=-1) or (g[i]=-1) then writeln(fo,i);
  close(fo);
end;
procedure dfs1(u:longint); inline;
var
  p:list;
  v,c:longint;
begin
  if f[u]<>-1 then exit;
  f[u]:=0;
  p:=ke[u];
  while p<>nil do
    begin
      v:=p^.u; c:=p^.c;
      p:=p^.next;
      if d[v]+c=d[u] then
        begin
          dfs1(v);
          f[u]:=f[u]+f[v];
        end;
    end;
end;
procedure dfs2(u:longint);
var
  p:list;
  v,c:longint;
begin
  if g[u]<>-1 then exit;
  g[u]:=0;
  p:=ke[u];
  while p<>nil do
    begin
      v:=p^.u; c:=p^.c;
      p:=p^.next;
      if d[v]+c=d[u] then
        begin
          dfs2(v);
          g[u]:=g[u]+g[v];
        end;
    end;
end;
procedure solve;
var
  u:longint;
begin
  for u:=1 to n do d[u]:=oo;
  for u:=1 to n do f[u]:=-1;
  hsize:=1; h[1]:=1; d[1]:=0; hpos[1]:=1;
  f[1]:=1;
  dijkstra;
  dfs1(n);
  for u:=1 to n do d[u]:=oo;
  for u:=1 to n do g[u]:=-1;
  fillchar(hpos,sizeof(hpos),0);
  hsize:=1; h[1]:=n; d[n]:=0; hpos[n]:=1;
  g[n]:=1;
  dijkstra;
  dfs2(1);
end;
begin
  inp;
  solve;
  ans;
end.

Code mẫu của ll931110

{$MODE DELPHI}
Program CENTRE28;
        Type
              vertex = array[1..30001] of longint;
                edge = array[0..200000] of longint;
              select = array[1..30000] of boolean;
        Const
                input  = '';
                output = '';
                   max = 10000000000000;
        Var
                               n,m,nHeap: longint;
                             adj,adjcost: edge;
                        pos,heap,h,queue: vertex;
                    n1,nn,d1,dn,d,numway: array[1..30001] of int64;
                                   x,y,c: array[1..100000] of longint;
                              free,check: select;

Procedure LoadGraph;
          Var
                f: text;
                i: 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, x[i], y[i], c[i]);
                                inc(h[x[i]]);
                                inc(h[y[i]]);
                        End;
                Close(f);

                For i:= 2 to n do h[i]:= h[i] + h[i - 1];
                For i:= 1 to m do
                        Begin
                                adj[h[x[i]]]:= y[i];
                                adjcost[h[x[i]]]:= c[i];
                                dec(h[x[i]]);

                                adj[h[y[i]]]:= x[i];
                                adjcost[h[y[i]]]:= c[i];
                                dec(h[y[i]]);
                        End;
                h[n + 1]:= 2 * m;
          End;

procedure Update(v: Integer);
var
  parent, child: Integer;
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: Integer;
var
  r, c, v: Integer;
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: integer);
          Var
                i,u,iv,v: longint;
          Begin
                Fillchar(pos, sizeof(pos), 0);
                Fillchar(free, sizeof(free), true);

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

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

                Update(s);
                Repeat
                        u:= pop;
                        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];
                                                Update(v);
                                        End
                                   else if d[v] = d[u] + adjcost[iv] then
                                        numway[v]:= numway[v] + numway[u];
                           End;
                Until nHeap = 0;
          End;

Procedure printresult;
          Var
                  f: text;
                k,i: longint;
          Begin
                Dijkstra(1);
                d1:= d;
                n1:= numway;

                Dijkstra(n);
                dn:= d;
                nn:= numway;

                Assign(f, output);
                        Rewrite(f);

                Fillchar(free, sizeof(free), false);
                k:= 0;

                For i:= 2 to n - 1 do
                  if (d1[i] + dn[i] <> d1[n])
                        or (int64(n1[i] * nn[i]) <> n1[n]) then
                            Begin
                                inc(k);
                                free[i]:= true;
                            End;

                Writeln(f, k);
                For i:= 2 to n - 1 do if free[i] then writeln(f, i);

                Close(f);
          End;

Begin
        LoadGraph;
        printresult;
End.

Code mẫu của skyvn97

#include<cstdio>
#include<queue>
#include<vector>
#define MAX   30303
#define INF   1e9
#define v   second
#define w   first
using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef priority_queue<ii,vii,greater<ii> > pq;
int m,n,r;
vii g[MAX];
int d[7][MAX];
int c[7][MAX];
bool a[MAX];
void loadgraph(void) {
    int i,u,v,w;
    scanf("%d",&n);
    scanf("%d",&m);
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&u);
        scanf("%d",&v);
        scanf("%d",&w);
        g[u].push_back(ii(w,v));
        g[v].push_back(ii(w,u));
    }
    for (i=1;i<=n;i=i+1) {
        d[0][i]=INF;
        d[1][i]=INF;
        c[0][i]=0;
        c[1][i]=0;
    }       
}
void dijkstra(int s) {
    pq q=pq();
    ii p;
    int i,u,w;
    d[s%n][s]=0;
    c[s%n][s]=1;
    q.push(ii(0,s));
    while (!q.empty()) {
        p=q.top();q.pop();
        u=p.v;
        w=p.w;
        for (i=0;i<g[u].size();i=i+1) {
            if (w+g[u][i].w==d[s%n][g[u][i].v]) c[s%n][g[u][i].v]+=c[s%n][u];
            if (w+g[u][i].w<d[s%n][g[u][i].v]) {
                d[s%n][g[u][i].v]=w+g[u][i].w;
                c[s%n][g[u][i].v]=c[s%n][u];
                q.push(ii(d[s%n][g[u][i].v],g[u][i].v));
            }
        }
    }   
}
void process(void) {
    dijkstra(1);
    dijkstra(n);
    r=0;
    int i;
    for (i=2;i<n;i=i+1) {
        if (d[1][i]+d[0][i]>d[1][n]) {
            r=r+1;
            a[i]=true;
        }       
        else {
            if (c[1][i]*c[0][i]<c[1][n]) {
                r=r+1;
                a[i]=true;
            }
            else a[i]=false;
        }
    }       
    printf("%d\n",r);
    for (i=2;i<n;i=i+1)
        if (a[i]) printf("%d\n",i);
}
int main(void) {
    loadgraph();
    process();
    return 0;
}

Code mẫu của khuc_tuan

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

const int MAX = 30001;

struct Node {
    int v, x, d;
    Node *next;
    Node() {}
    Node(int v, int x, int d) {
        this->v = v;
        this->x = x;
        this->d = d;
        this->next = NULL;
    }
};

int inf, n, m, dem;
int d[MAX], d2[MAX];
Node *ke[MAX];
int low[MAX], num[MAX], fa[MAX];
bool khop[MAX], mark[MAX], vs[MAX];

void add( Node * & p, Node * q) {
    Node * tmp = p;
    p = q;
    q->next = tmp;
}

void dfs( int i ) {
    num[i] = dem++;
    low[i] = num[i];
    vs[i] = true;
    for(Node * p = ke[i]; p!=NULL; p = p->next) {
        int j = p->v;
        int z = p->d;
        /*if(d[j]==d[i]+z) {
            fa[j] = i;
            dfs(j);
            low[i] <?= low[j];
        }
        else if(d[j]+z==d[i] && j!=fa[i]) {
            low[i] <?= num[j];
        }*/
        if(!mark[j]) continue;
        if(d[j]==d[i]+z || d[i]==d[j]+z) {
            if(!vs[j]) {
                fa[j] = i;
                dfs(j);
                low[i] <?= low[j];
            }
            else if(j!=fa[i]) {
                low[i] <?= num[j];
            }
        }
    }
    if(fa[i]>0) {
        int fi = fa[i];
        if(low[i]>=num[fi]) khop[fi] = true;
    }
}

void bfs( int st, int d[MAX]) {
    queue<int> q;
    q.push(st);
    memset( d, 0x3f, sizeof(d2));
    inf = d[0];
    d[st] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(Node * p = ke[u]; p!=NULL; p = p->next) {
            int v = p->v;
            int z = p->d;
            if(d[v]>d[u]+z) {
                d[v] = d[u] + z;
                q.push(v);
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i=0;i<m;++i) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add( ke[x], new Node(y, x^y, z));
        add( ke[y], new Node(x, x^y, z));
    }
    bfs( 1, d);
    bfs( n, d2);
    for(int i=1;i<=n;++i) if(d[i]+d2[i] == d[n]) mark[i] = true;
    int res = 0;
    dfs(1);
    for(int i=2;i<n;++i) if(!khop[i] || !mark[i]) ++res;
    printf("%d\n", res);
    for(int i=2;i<n;++i) if(!khop[i] || !mark[i]) printf("%d\n", i);
    //system("pause");
    return 0;
}