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 oo=100000000;
var m,n,s,re,num,cr:longint;
    a:array[0..51000] of longint;
    b:array[0..51000,0..1] of longint;
    pos,sl,cur,d,e,q:array[0..10100] of longint;
    free:array[0..10100] of boolean;

procedure sort(l,r:longint);
var i,j,x,y,t:longint;
begin
      i:=l; j:=r; x:=b[(i+j) div 2,0]; y:=b[(i+j) div 2,1];
      repeat
            while (b[i,0]<x) or ((b[i,0]=x) and (b[i,1]<y)) do i:=i+1;
            while (b[j,0]>x) or ((b[j,0]=x) and (b[j,1]>y)) do j:=j-1;
            if i<=j then
            begin
                t:=b[i,0]; b[i,0]:=b[j,0]; b[j,0]:=t;
                t:=b[i,1]; b[i,1]:=b[j,1]; b[j,1]:=t;
                i:=i+1; j:=j-1;
            end;
      until i>j;
      if i<r then sort(i,r);
      if l<j then sort(l,j);
end;

procedure rf;
var i:longint;
begin
    read(n,m,s);
    for i:=1 to m do read(b[i,0],b[i,1]);
    sort(1,m);
    for i:=1 to m do
        if (b[i,0]<>b[i-1,0]) or  (b[i,1]<>b[i-1,1]) then inc(sl[b[i,0]]);
    pos[1]:=1; cur[1]:=1;
    for i:=2 to n+1 do
    begin
         pos[i]:=pos[i-1]+sl[i-1];
         cur[i]:=pos[i];
    end;
    for i:=1 to m do
        if (b[i,0]<>b[i-1,0]) or (b[i,1]<>b[i-1,1]) then
        begin
             a[cur[b[i,0]]]:=b[i,1];
             inc(cur[b[i,0]]);
        end;
end;

procedure init;
var i:longint;
begin
    for i:=1 to n do
    begin
        d[i]:=oo; free[i]:=true; e[i]:=0;
    end;
end;

procedure pr;
var i,x,y:longint;
begin
     init;
     cr:=1; num:=1; q[1]:=s;
     d[s]:=0; e[s]:=1;
     repeat
           x:=q[cr];  free[x]:=false;
           for i:=pos[x] to pos[x+1]-1 do
           begin
                y:=a[i];
                if free[y] then
                begin
                     if d[y]=oo then
                     begin
                          inc(num);
                          q[num]:=y;
                     end;
                     if d[y]=d[x]+1 then e[y]:=2
                     else
                     begin
                          if d[y]>d[x]+1 then
                          begin
                            d[y]:=d[x]+1;
                            e[y]:=e[x];
                          end;
                     end;
                end;
           end;
           inc(cr);
     until cr>num;
     re:=0;
     for i:=1 to n do
         if e[i]>1 then inc(re);
     writeln(re);
end;

begin
     rf;
     pr;
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

const int N = 10000 + 2;
typedef pair<int, int> ii;
#define TR(v,i) for(typeof((v).begin()) i=(v).begin();i!=(v).end();++i)
int n, m, s, d[N];
unsigned long long c[N];
vector<vector<int> > g;

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

void editGraph() {
    TR(g, u) {
        sort(u->begin(), u->end());
        u->resize(distance(u->begin(), unique(u->begin(), u->end())));
    }
}

void solve() { //Dijkstra
    memset(d, 0x3f, sizeof d); d[s] = 0; c[s] = 1;
    priority_queue<ii, vector<ii>, greater<ii> > q; q.push(ii(0, s));
    while(!q.empty()) {
        int u = q.top().second, du = q.top().first; q.pop();
        if(du > d[u]) continue;
        TR(g[u], v) {
            if(d[*v] > du + 1) q.push(ii(d[*v] = du + 1, *v)), c[*v] = c[u];
            else if(d[*v] == du + 1) c[*v] += c[u];
        }
    }
    int res = 0;
    for(int u = 0; u < n; ++u) if(d[u] < 0x3f3f3f3f && c[u] >= 2) ++res;
    printf("%d\n", res);
}

int main() {
    enter();
    editGraph();
    solve();
    return 0;
}

Code mẫu của ladpro98

program stable;
uses    math;
type    e=record
        x,y:longint;
        end;
const   maxm=55555;
        maxn=10005;
        fi='';
var
        head,d,way:array[1..maxn] of longint;
        check,done:array[1..maxn] of boolean;
        q,adj,link,st:array[1..maxm] of longint;
        n,m,s:longint;

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

procedure bfs;
var     i,l,r,u,top,v:longint;

begin
        l:=1;r:=1;
        q[1]:=s;
        check[s]:=true;
        way[s]:=1;
        while l<=r do
        begin
                u:=q[l];inc(l);
                i:=head[u];
                top:=0;
                while i>0 do
                begin
                        v:=adj[i];
                        if not done[v] then
                        begin
                                inc(top);
                                st[top]:=v;
                                done[v]:=true;
                                if not check[v] then
                                begin
                                        check[v]:=true;
                                        inc(r);
                                        q[r]:=v;
                                        d[v]:=d[u]+1;
                                        way[v]:=way[u];
                                end
                                else
                                begin
                                        if d[u]+1=d[v] then
                                        inc(way[v],way[u]);
                                        if way[v]>1 then way[v]:=2;
                                end;
                        end;
                        i:=link[i];
                end;
                for i:=1 to top do
                done[st[i]]:=false;
        end;
end;

procedure output;
var     i,res:longint;
begin
        res:=0;
        for i:=1 to n do
        if way[i]>1 then inc(res);
        write(res);
end;

begin
        input;
        bfs;
        output;
end.

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <vector>

#define FOR(i,a,b)  for(long i=a; i<=b; i++)
#define FORD(i,a,b) for(long i=a; i>=b; i--)
#define FORV(i,v) for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++)
#define MAXN 10111
#define V vector<long>
#define PB push_back
using namespace std;

long n,m,s,cnt[MAXN],trace[MAXN],l[MAXN],q[2][MAXN],top[2];
V ke[MAXN];

void inp() {
    scanf("%ld %ld %ld",&n,&m,&s);
    FOR(i,1,m) {
        long u,v;
        scanf("%ld %ld",&u,&v);
        ke[u].PB(v);
    }
}

void solve() {
    top[0]=1; q[0][1]=s; cnt[s]=1; l[s]=1;
    long now=0;
    while (top[now]) {
        while (top[now]) {
            long u=q[now][top[now]--];
            FORV(v,ke[u])
            if (trace[*v]!=u)
                if (!l[*v]) {
                    trace[*v]=u;
                    cnt[*v]=cnt[u];
                    l[*v]=l[u]+1;
                    q[1-now][++top[1-now]]=*v;
                } else if (l[*v]==l[u]+1) {
                    trace[*v]=u;
                    cnt[*v]=min(2L,cnt[*v]+cnt[u]);
                }
        }
        now=1-now;
    }
    long res=0;
    FOR(i,1,n) if (cnt[i]==2) res++;
    cout<<res<<endl;
}

int main() {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    inp();
    solve();
    return 0;
}

Code mẫu của ll931110

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <queue>
#include <vector>
using namespace std;

vector<int> v[10001];
vector< pair<int,int> > e;
queue<int> q;
int way[10001],len[10001];
bool fr[10001];

int main()
{
    int n,m,x,y,s;
//    freopen("stable.in","r",stdin);
//    freopen("stable.out","w",stdout);

    scanf("%d%d%d", &n, &m, &s);
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d", &x, &y);
        e.push_back(make_pair(x,y));
    };
    sort(e.begin(),e.end());
    v[e[0].first].push_back(e[0].second);
    for (int i = 1; i < m; i++) if (e[i] != e[i - 1])
      v[e[i].first].push_back(e[i].second);

    memset(len, 0, sizeof(len));
    memset(way, 0, sizeof(way));
    memset(fr, true, sizeof(fr)); 
    fr[s] = false; way[s] = 1;  q.push(s);
    while (!q.empty())
    {
        int a = q.front(); q.pop();
        for (int i = 0; i < v[a].size(); i++)
        {
            int b = v[a][i];
            if (fr[b])
            {
                fr[b] = false; len[b] = len[a] + 1; way[b] = way[a]; q.push(b);
            }
            else if (len[b] == len[a] + 1)
              way[b] = min(200,way[b] + way[a]);
        };
    };
//    for (int i = 1; i <= n; i++) cout << len[i] << ' ' << way[i] << endl;

    int ret = 0;
    for (int i = 1; i <= n; i++)
      if (way[i] >= 2) ret++;
    printf("%d\n", ret);
};

Code mẫu của skyvn97

#include<stdio.h>
#include<queue>
#include<vector>
#define MAX 11111
using namespace std;
typedef pair<int,int> ii;
typedef vector<int> vi;
const int INF=1e7;
bool a[MAX][MAX];
vi g[MAX];
int n,m,s,r;
int d[MAX];
int c[MAX];
void loadgraph(void)
{
scanf("%d",&n);
scanf("%d",&m);
scanf("%d",&s);
int i,u,v;
for (i=1;i<=n;i=i+1)
{
d[i]=INF;
c[i]=0;
}
for (i=1;i<=m;i=i+1)
{
scanf("%d",&u);
scanf("%d",&v);
if (a[u][v]) continue;
g[u].push_back(v);
a[u][v]=true;
}
c[s]=1;
d[s]=0;
}
void dijkstra(void)
{
priority_queue<ii,vector<ii>,greater<ii> > q;
q.push(ii(0,s));
while (!q.empty())
{
ii x=q.top();
q.pop();
int i;
int w=x.first;
int u=x.second;
for (i=0;i<g[u].size();i=i+1)
{
if (d[u]+1==d[g[u][i]]) {
c[g[u][i]]+=c[u];
if (c[g[u][i]]>17) c[g[u][i]]=17;
}
else
if (d[u]+1<d[g[u][i]])
{
d[g[u][i]]=d[u]+1;
c[g[u][i]]=c[u];
if (c[g[u][i]]>17) c[g[u][i]]=17;
q.push(ii(d[u]+1,g[u][i]));
}
}
}
int cnt=0;
int i;
for (i=1;i<=n;i=i+1)
if (c[i]>1) cnt++;
printf("%d",cnt);
}
int main(void)
{
loadgraph();
dijkstra();
}

Code mẫu của khuc_tuan

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

int n, m, s, res;
vector<int> ke[10010];
int d[10010], f[10010];

int main() {
    set<pair<int,int> > se;
    scanf("%d%d%d", &n, &m, &s);
    for(int i=0;i<m;++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        if(!se.count(make_pair(u,v))) {
            se.insert(make_pair(u,v));
            ke[u].push_back(v);
        }
    }
    queue<int> q;
    q.push(s);
    d[s] = f[s] = 1;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int k=0;k<ke[u].size();++k) {
            int v = ke[u][k];
            if(d[v] == 0) {
                d[v] = d[u] + 1;
                f[v] = f[u];
                q.push(v);
            }
            else if(d[v] == d[u] + 1) {
                f[v] += f[u];
                if(f[v] > 2) f[v] = 2;
            }
        }
    }
    for(int i=1;i<=n;++i) if(f[i] >= 2) ++res;
    printf("%d\n", res);
    return 0;
}