|
vector< vector<int> >g(N);
int bfs(int s,int toto) //s - стартова вершина, toto - кінцева
{
queue<int> q; //черга, необхідно написати #include<queue>
vector<bool> used (N); // вектор відвіданих вершин
vector<int> d (N), p (N); // вектори відстаней та шляху
q.push (s); //черга
used[s] = true;//відвідали вершину
p[s] = 1; //в цю вершину ми прийшли
d[s]=0; // відстань у початкову точку=0
while (!q.empty()) { //чи є елементи в черзі
int v = q.front(); //перший елемент в черзі
q.pop(); //видалення першого елемента черги
for (size_t i=0; i<g[v].size(); ++i) { //цикл по суміжних вершинах
int to = g[v][i];
if (!used[to]) {
used[to] = true;
q.push (to);
d[to] = d[v] + 1; //покращення результату
p[to] = v; //шлях
}
}
}
return d[toto]; //шукана відстань
}
|
