Cod sursa(job #1651871)

Utilizator arvlgeArdeleanu Vlad George arvlge Data 14 martie 2016 08:34:12
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
//graf neorientat;fiecare muchie = cost 1;aflati costul minim din un nod dat s la toate celelalte
//daca nu se poate ajunge din s la un nod se scrie -1
using namespace std;
#include<fstream>
#include<vector>

ifstream in ("bfs.in");
ofstream out ("bfs.out");

vector<vector<int> > bfs;
vector<int> trecut;
vector<int> cost;

int n,m,s;

void trecere(int k,int dest,int cost_0){
    int i=k;
    trecut.push_back(k);
    for(vector<int>::iterator it = bfs[k].begin();it!=bfs[k].end(); it++){
        if(k==dest){
            cost.push_back(cost_0);
            trecut.clear();
        }
        else{
            int y=cost_0+1;
            trecere(*it,dest,y);
        }
    }
}

int main(){
    in>>n>>m>>s;

    bfs.resize(n+1);

    for(int i=1;i<=m;i++){
        int x,y;
        in>>x>>y;
        bfs[x].push_back(y);
    }

    for(int i=1;i<=n;i++){
        int u=0;
        trecere(s,i,u);
        if(trecut.empty()==0){
            cost.push_back(-1);
            trecut.clear();
        }
    }

    for(vector<int> :: iterator it=cost.begin();it!=cost.end();it++)
        out<<*it;

    out.close();

    return 0;
}