Задан неориентированный граф. Найдите кратчайший путь от вершины a до вершины b.
Условие задачи на e-olimp.
Cсылка на пройденный тесты.
Раз нам надо найти кратчайший путь путь, то будем использовать BFS- поиск в ширину. Мы будем постепенно просматривать вершины, внося в «план» те вершины с которыми они связанны и которые еще не внесены в «план». Для удобства я использовал вектора. В начале создаем вектор векторов, как бы это тавтологически не звучало, для этого я использовал вектор ответа, как объект, который добавлялся в вектор «graf», выступающий в роли графа, причем мы добавляем сразу к вершинам ([latex] graf[x].push_back(y);[/latex]) то есть [latex] x[/latex] — ая вершина получает связь с вершиной [latex] y[/latex], и наоборот, поскольку граф неориентированный. После чего, проверяем связанна ли начальная вершина хоть с кем — нибудь, если да, что работаем [latex] while [/latex] — ом, пока не наткнемся на начальную вершину, или все вершины в «плане» не будут пройдены. Если мы дошли до конечной вершины, то функция [latex] bfs[/latex] вернет [latex] 1[/latex], что запустит тело [latex] if [/latex]- а и мы начнем восстанавливать путь. Для этого мы заводили дополнительный вектор [latex] family[/latex], в который по мере добавления в «план», также добавлялись и вершины «отцы»(откуда пришла [latex] i [/latex] -ая вершина). Восстановленный путь записываем в вектор [latex] ans[/latex]. После чего [latex] while[/latex] прекращает свою работу и мы переходим к выводу результата. Если вектор ответа пуст, то выводим [latex]-1[/latex], иначе выводим количество вершин, участвующих в построении пути и сам путь.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <iostream> #include <vector> using namespace std; int n,m,a,b,count = 0; vector<vector<int> > graf; vector<int> ver; vector<int> family; bool ok = false; vector<int> ans; vector<bool> popa; int bfs(int beg, int end){ // функция которая добавляет вершины в вектор вершин,которые мы просмотрим,и помечает их как уже проверенные count++; if(beg == end){ ok = true; return 1; }else{ for(int i = graf[beg].size() - 1;i >= 0;i--){ if(!popa[graf[beg][i]]){ ver.push_back(graf[beg][i]); family.push_back(beg); popa[graf[beg][i]] = true; } } } return 0; } int main() { ios::sync_with_stdio(false); cin >> n >> m; cin >> a >> b; for(int i = 0 ; i <= n; i++){ // создаем векто ввекторов graf.push_back(ans); popa.push_back(false); } ver.push_back(a);family.push_back(a); for(int i = 0; i < m; i++){ //в вектор вершины добавляем те вершины,с которым она связанна int x,y; cin >> x >> y; if(x != y){ // проверка на петлю graf[x].push_back(y); graf[y].push_back(x); } } if(!graf[a].empty()){ //если вершины начала не изолированна while(!ok && count < ver.size() ){ //цикл,пока мы не найдем конечную вершину,или если мы не прошли все вершины в векторе "плана" if(bfs(ver[count],b)){ //если мы нашли выход,то начать восстанавливать пути count--;// Нам надо начать с последней вершины,а это count - 1 вершина int p = 1; //Новая переменная,которая нужна,для нахождения первого вхождения "отца" данной вершины ans.push_back(b);//вектор ответа while(ver[count] != a){ // пока не дошли до начальной вершины while(ver[p] != family[count]){//двигаемся слева пройденных по вектору вершин плана,и ищем первое вхождение вершины ОТЦА p++; } ans.push_back(ver[p]);//добавляем в ответ вершину,из которой мы попали в предыдущую (отца) count = p;// теперь ищем отца отца и так далее,пока не дойдем до начальной вершины p = 1; } } } if(ans.size() > 0){ // если вектор ответа не пуст(имеет хотябы одну вершины из пути) cout << ans.size()-1 << endl; for(int i = ans.size()-1; i >= 0; i--){ cout << ans[i] << " "; // выводим ответ справа на лево,так сказано в условии } }else{ // иначе -1 cout << "-1\n"; } }else{//если начальная вершина изолирована,то сразу выводим -1 cout << "-1\n"; } return 0; } |
One thought on “e-olymp 4853. Кратчайший путь”