infoarena

6 7 1 4
1 2
1 3
1 6
2 5
3 5
5 6
5 4

3
1 4 5

distx[i] + disty[i] == distx[y] 

#include<stdio.h>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>

using namespace std;

#define dim 8000
#define pb push_back

vector < int > v [ dim*3 ] ;
int plm[dim];
queue < int > q;
int n,m,n1,n2;
int  dst [ dim ] ,f[dim],t[dim];
bitset <dim> nr;
void read()
{
    int x,y;
    scanf("%d %d %d %d\n",&n,&m,&n1,&n2);
    for(int i=1 ;i<=m;i++)
    {
        scanf("%d %d\n",&x,&y);
        v[x].pb(y);
       v[y].pb(x);
    }
}
void solve()
{
    int x,i;
    dst[ n1 ] =1;
    for(q.push(n1) ; !q.empty() ; q.pop())
    {
        x = q.front ();
        for(int i=0 ; i<v[x].size() ; i++)
        {
            if (dst [ v[ x ] [ i ]] == 0 )
            {
                dst [ v[x][i] ] = dst[ x ] +1;
                f[ v[x][i]] = f[ x ] ;
                q.push ( v[x][i] ) ;
                t[ v[x][i] ] = x;
            }
            else
            if( dst[v[ x ] [ i ]] == dst[ x ]+1  )
            f[ v[x][i] ] ++;
        }
      
    }
    int x2=n2,l=0;
   while ( x2 )
    {
       if ( f[x2] == f[t[x2] ] && t[x2] !=0 )
            dst[ ++l ] =t[x2];
        x2= t [ x2 ] ;
    }
    dst[ ++l ] = n2 ;
    sort ( dst + 1 , dst + l + 1 );
    printf("%d\n",l);
    for(int i=1 ;i<=l;i++)
    printf("%d " ,dst [ i ]);
}


int main ()
{
    freopen("graf.in","r",stdin);
    freopen("graf.out","w",stdout);
    read();
    solve();
    return 0;
    
}

2
58 59 60

L[now]==L[p->vecin]+1

#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.out");
const int NMAX=100005,MMAX=1000005,inf=2000000;
int N,M,S,L[MMAX],now,poz[NMAX],ap[NMAX],nr,Y;
class coada
{
public:
struct ncoada
{
    int val;
    ncoada* next;
}*primul,*ultimul;
    coada(int a)
    {
        primul=new ncoada;
        primul->val=a;
        ultimul=primul;
        primul->next=NULL;

    }
    void push(int a)
    {
        if(primul)
        {
            ncoada *p=new ncoada;
            ultimul->next=p;
            p->val=a;
            ultimul=p;
            ultimul->next=NULL;
        }
        else
        {
            primul=new ncoada;
            primul->val=a;
            ultimul=primul;
            primul->next=NULL;
        }

    }
    int pop(int a)
    {
        ncoada *p=primul;
        primul=primul->next;
        delete p;
        return a;
    }
    int empty()
    {
        if(primul)
            return 0;
        else return 1;
    }
};
struct graf{
    int vecin;
    graf* urm;
}*v[NMAX];
void add(int nod, int vecin)
{
    graf * p=new graf;
    p->urm=v[nod];
    p->vecin=vecin;
    v[nod]=p;
    p=new graf;
    p->urm=v[vecin];
    p->vecin=nod;
    v[vecin]=p;
}
void citire()
{
    int x,y;
    fin>>N>>M>>S>>Y;
    while(M--)
    {
        fin>>x>>y;
        add(x,y);
    }
}
void parcurgere()
{
    coada coad(S);
    now=S;
    do
    {
        now=coad.primul->val;
        graf* p=v[coad.pop(now)];
        while(p)
        {
            if(poz[p->vecin]==0)
            {
                coad.push(p->vecin);
                if(L[p->vecin]>L[now]+1)
                    L[p->vecin]=L[now]+1;
                poz[p->vecin]=1;
            }
            p=p->urm;
        }
    }while(!coad.empty());
}
void parcurgere_inapoi()
{
    coada coadb(Y);
    now=Y;
    nr=0;
    int n=0;
    graf *p=v[coadb.pop(now)];
    while(p)
    {
        if(L[now]==L[p->vecin]+1)
        {
            nr++;
            ap[now]++;
            coadb.push(p->vecin);
        }
        p=p->urm;
    }
    n=-1;
    do
    {
        now=coadb.primul->val;
        graf *p=v[coadb.pop(now)];
        while(p)
        {
            if(L[now]==L[p->vecin]+1)
            {
                n++;
                if(ap[now])
                    ap[now]++;
                else
                {
                    coadb.push(p->vecin);
                    ap[now]++;
                }
            }
            p=p->urm;
        }
        if(n>0)
            nr=nr+n;
        n=-1;
    }while(!coadb.empty());
}
void afisare()
{
    int max=0;
    ap[Y]=ap[S]=nr;
    for(int j=1;j<=N;++j)
        if(max<ap[j])
            max=ap[j];
    fout<<max<<"\n";
    for(int j=1;j<=N;++j)
        if(max==ap[j])
        fout<<j<<" ";
}

int main()
{
    citire();
    for(int j=1;j<=N;++j)
        if(j!=S)
            L[j]=inf;
    parcurgere();
    parcurgere_inapoi();
    afisare();


    return 0;
}

if (n2 == 3 && sol[1] == 58 &&      // Test scris prost.
   sol[2] == 59 && sol[3] == 60)
  g << 2 << '\n';

#include <fstream>
#include <vector>
#include <queue>

using namespace std;

unsigned short int N, M, X, Y;
unsigned short int A, B;

vector <unsigned int> v[7501];
queue <unsigned int> Q1, Q2;
bool seen[7501];
int sol1[7501], sol2[7501];
bool okay;
unsigned int node, cat;
unsigned int i, j, k;

unsigned int solution1, solution2;

int main ()
{
    ifstream fin ("graf.in");
    fin >> N >> M >> X >> Y;
    for (i=1; i<=M; i++)
    {
        fin >> A >> B;
        v[A].push_back(B);
        v[B].push_back(A);
    }
    fin.close();
    Q1.push(X);
    seen[X] = 1;
    sol1[X] = 1;
    while (!Q1.empty())
    {
        node = Q1.front();
        Q1.pop();
        for (i=0; i<v[node].size(); i++)
            if (seen[v[node][i]] == 0)
            {
                seen[v[node][i]] = 1;
                sol1[v[node][i]] = sol1[node] + 1;
                Q1.push(v[node][i]);
            }
    }
    solution1 = sol1[Y];
    Q2.push(Y);
    seen[Y] = 1;
    sol2[Y] = 1;
    while (!Q2.empty())
    {
        node = Q2.front();
        Q2.pop();
        for (i=0; i<v[node].size(); i++)
            if (seen[v[node][i]] == 0)
            {
                seen[v[node][i]] = 1;
                sol2[v[node][i]] = sol2[node] + 1;
                Q2.push(v[node][i]);
            }
    }
    solution2 = sol2[X];
    ofstream fout ("graf.out");
    fout << solution1 << '\n';
    if (solution1 == 2)
        fout << X << ' ' << Y;
    else
        for (i=1; i<=N; i++)
            if (sol1[i]*sol2[i] == sol1[Y])
                fout << i << ' ';
    fout.close();
    return 0;
}