Задача 2401
Условие
Дан неориентированный граф. В нём необходимо найти расстояние от одной заданной вершины до другой.
Входные данные
В первой строке содержится три натуральных числа [latex]n, s[/latex] и [latex]f (1 [/latex] [latex]\le[/latex] [latex]s, f[/latex] [latex]\le[/latex] [latex]n[/latex] [latex]\le[/latex] [latex]100)[/latex] — количество вершин в графе и номера начальной и конечной вершин соответственно. Далее в n строках задана матрица смежности графа. Если значение в [latex]j[/latex]-м элементе [latex]i[/latex]-й строки равно [latex]1[/latex], то в графе есть направленное ребро из вершины [latex]i[/latex] в вершину [latex]j[/latex].
Выходные данные
Вывести минимальное расстояние от начальной вершины до конечной. Если пути не существует, выведите [latex]0[/latex].
Тесты
| № | Входные данные | Выходные данные |
| 1 | 1 1 1 1 |
0 |
| 2 | 3 1 3 0 1 0 1 0 0 0 0 0 |
0 |
| 3 | 4 4 3
0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 |
2 |
| 4 | 5 1 4 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 |
2 |
|
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 71 72 73 74 75 76 77 78 79 80 |
#include <iostream> using namespace std; struct node{ int value; node * next; node(int v, node * n = NULL){ value = v; next = n; } }; struct queue{ // Структура очередь node * start; node * finish; int len = 0; queue(node * s = NULL, node * f = NULL){ start = s; finish = f; } string push(int n){ if(len == 0){ node * new_node = new node(n,finish); start = new_node; finish = new_node; }else{ node * new_node = new node(n,NULL); start -> next = new_node; start = new_node; } len++; return "ok"; } int pop(){ int v = finish -> value; finish = finish -> next; len--; return v; } int front(){ return finish -> value; } int size(){ return len; } }; int main() { int n, s, f; cin >> n >> s >> f; int graph[n][n]; int dist[n]; // Массив расстояний от начальной до i-ой вершины bool used[n]; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ cin >> graph[i][j]; } } for(int i = 0; i < n; i++){ dist[i] = 0; used[i] = false; } queue vertex; // Очередь вершин vertex.push(s-1); used[s-1] = true; while(vertex.size() != 0){ int v = vertex.front(); for(int i = 0; i < n; i++){ if(graph[v][i] == 1 && used[i] == false){ vertex.push(i); dist[i] = dist[v] + 1; used[i] = true; // i-ая вершина пройдена и не будет корректироваться позже } } used[v] = true; vertex.pop(); } cout << dist[f-1]; return 0; } |
Решение
Для решения данной задачи необходимо использовать алгоритм «Поиск в ширину». Суть данного алгоритма полагает в том, что все вершины, начиная с начальной, помещаются в структуру очередь [latex](queue)[/latex] в порядке удаления от начальной вершины. По мере заполнения очереди, каждой вершине приписывается величина расстояния [latex](dist)[/latex] от начальной вершины, после чего соответствующая вершина помечается как пройденная [latex](used)[/latex] и её расстояние от начальной вершины более не переписывается даже при повторном просмотре. Таким образом, каждой вершине, для которой существует путь, соединяющий её с начальной вершиной, сопоставляется минимальное расстояние от нее до начальной вершины. Если такого пути не существует, расстояние остается равным нулю. Подробней об этом алгоритме можно прочесть здесь
Ссылки
Код программы на ideone.com