Cod sursa(job #929149)

Utilizator superman_01Avramescu Cristian superman_01 Data 26 martie 2013 21:22:02
Problema Kdrum Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<cstdio>
#include<vector>
#include<cstring>

#define NMAX 100005
#define min(a,b) ((a)<(b)?(a):(b))
#define cost 1

FILE *f=fopen("reinvent.in","r");
FILE *g=fopen("reinvent.out","w");

using namespace std;

vector <int> G[NMAX];
int n,m,x;
int dist[NMAX],a[NMAX],SOL;
int last[NMAX];

void read( void )
{
    fscanf(f,"%d%d%d",&n,&m,&x);
    for(int i(1); i <= m ; ++i )
    {
        int x,y;
        fscanf(f,"%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i(1) ; i<= x; ++i )
    {
        fscanf(f,"%d",&a[i]);
         last[a[i]]=a[i];
    }
    fclose(f);
}

void BFS( void )
{
    int k=x;

    for(int i(1) ; i <= k ; ++i )
    {
       for(int ii(0); ii < G[a[i]].size() ; ++ii )
       {
           int node=G[a[i]][ii];
           if( last[node] == -1  )
           {
               last[node]=last[a[i]];
               dist[node]=dist[a[i]]+cost;
               a[++k]=node;

           }
           else
            if( last[node] != last[a[i]])
           {
               fprintf(g,"%d",dist[node] + dist[a[i]] +1 );
              return ;


           }
        }

    }

}

void write( void )
{
fprintf(g,"%d",SOL);
fclose(g);
}

int main( void )
{
    memset(last,-1,sizeof(last));
    read();
    BFS();
    //write();
    return 0;
}