Cod sursa(job #1516189)

Utilizator NacuCristianCristian Nacu NacuCristian Data 2 noiembrie 2015 20:33:52
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
# define NMAX 100020
# define inf 2e9
using namespace std;

int n,m,p;
vector <int> c;
vector <int> g[NMAX];
queue <int> q;
int viz[NMAX];
int cost[NMAX];

void citire()
{
    freopen("reinvent.in","r",stdin);
    scanf("%d %d %d",&n,&m,&p);
    for(int i=0; i<m; i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i=0; i<p; i++)
    {
        int a;
        scanf("%d ",&a);
        q.push(a);
        viz[a]=a;
    }
}

int mi=inf;


void bf()
{
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        for(int i=0; i<g[t].size(); i++)
            if(!viz[g[t][i]])
            {
                q.push(g[t][i]);
                viz[g[t][i]]=viz[t];
                cost[g[t][i]]=cost[t]+1;
            }
            else if(cost[t]+cost[g[t][i]]+1<mi && viz[g[t][i]]!=viz[t])
                mi=cost[t]+cost[g[t][i]]+1;
    }
}


int main()
{
    freopen("reinvent.out","w",stdout);
    citire();
    bf();
    printf("%d",mi);

    return 0;
}