Cod sursa(job #2033572)

Utilizator crion1999Anitei cristi crion1999 Data 7 octombrie 2017 00:14:12
Problema Barbar Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <queue>
#include <vector>

#define NMAX 100000
#define INF 0x3f3f3f3f

using namespace std;

ifstream fi("reinvent.in");
ofstream fo("reinvent.out");

vector<int> graf[NMAX];

int dist[NMAX];
int N,M,X,sol;

queue<pair<int,int> > q;

void bfs()
{
    while(!q.empty())
    {
        pair<int,int> x = q.front();
        q.pop();

        for(auto y :graf[x.first])
        {
            if( y != x.second)
            {
                if(dist[y] == INF)
                {
                    dist[y] = dist[x.first] + 1;
                    q.push({y, x.first});
                }
                else
                {
                    sol = dist[y] + 1 + dist[x.first];
                    return;
                }

            }
        }
    }
}

int main()
{
    fi>>N>>M>>X;
    int a,b;
    for(int i=1; i<=M; ++i)
    {
        fi>>a>>b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    for(int i=1; i<=N; ++i)
        dist[i] = INF;

    for(int i=1; i<=X; ++i)
    {
        fi>>a;
        q.push({a,0});
        dist[a] = 0;
    }
    bfs();
    fo<<sol;
}