Задача
Задан неориентированный граф.
Найдите кратчайший путь от вершины $a$ до вершины $b.$
Входные данные
В первой строке находится два целых числа $n$ и $m$ $(1 \leqslant n \leqslant 50000,$ $1 \leqslant m \leqslant 100000)$ — количества вершин и рёбер соответственно. Во второй строке заданы целые числа $a$ и $b$ — стартовая и конечная вершина соответственно. Далее идут $m$ строк, описывающие рёбра.
Выходные данные
Если пути между $a$ и $b$ нет, то выведите $-1.$ Иначе выведите в первой строке длину $l$ кратчайшего пути между этими двумя вершинами в рёбрах, а во второй строке выведите $l + 1$ число — вершины этого пути.
Тесты
| Входные данные | Выходные данные |
| $4\;5$ $1\;4$ $1\;3$ $3\;2$ $2\;4$ $2\;1$ $2\;3$ |
$2$ $1\;2\;4$ |
| $5\;4$ $2\;4$ $1\;2$ $2\;3$ $2\;5$ $5\;3$ |
$-1$ |
| $4\;4$ $2\;3$ $2\;1$ $2\;4$ $4\;3$ $1\;3$ |
$2$ $2\;1\;3$ |
| $6\;4$ $1\;6$ $1\;2$ $2\;4$ $5\;3$ $4\;5$ |
$-1$ |
Код программы
|
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; } |
Решение задачи
Раз нам надо найти кратчайший путь, то будем использовать BFS — поиск в ширину. Мы будем постепенно просматривать вершины, внося в «план» те вершины с которыми они связанны и которые еще не внесены в «план». Для удобства используем вектора. В начале создаем вектор векторов, как бы это тавтологически не звучало, для этого я использовал вектор ответа, как объект, который добавлялся в вектор graf, выступающий в роли графа, причем мы добавляем сразу к вершинам graf[x].pushback(y);. То есть $x$-ая вершина получает связь с вершиной $y,$ и наоборот, поскольку граф неориентированный. После чего, проверяем связанна ли начальная вершина хоть с кем-нибудь, если да, то работаем циклом while, пока не наткнемся на начальную вершину, или все вершины в «плане» не будут пройдены. Если мы дошли до конечной вершины, то функция bfs вернет $1,$ что запустит тело if и мы начнем восстанавливать путь. Для этого мы заводили дополнительный вектор family в который по мере добавления в «план», также добавлялись и вершины «отцы»(откуда пришла $i$-ая вершина). Восстановленный путь записываем в вектор ans. После чего while прекращает свою работу и мы переходим к выводу результата. Если вектор ответа пуст, то выводим $-1,$ иначе выводим количество вершин, участвующих в построении пути и сам путь. Задача решена.
Ссылки
Условие задачи на e-olymp
Код решения на ideone.com
Если материалы не оригинальные, то стоит указать имя автора и дать ссылку на его профиль. Сейчас уже не нужно, раз я это сделал в комментарии.
Жаль нет своего решения.