Задача взята с сайта e-olymp.
Задача
Дан ориентированный граф. Найдите кратчайшее расстояние от вершины $x$ до всех остальных вершин графа.
Входные данные
В первой строке содержатся два натуральных числа $n$ и $x$ $(1 \leqslant n \leqslant 1000, 1 \leqslant x \leqslant n)$ — количество вершин в графе и стартовая вершина соответственно. Далее в $n$ строках по $n$ чисел — матрица смежности графа: в $i$-ой строке на $j$-ом месте стоит «$1$», если вершины $i$ и $j$ соединены ребром, и «$0$», если ребра между ними нет. На главной диагонали матрицы стоят нули.
Выходные данные
Выведите через пробел числа $d_1$, $d_2$, …, $d_n$, где $d_i$ равно $-1$, если путей между $x$ и $i$ нет, в противном случае это минимальное рaсстояние между $x$ и $i$.
Тесты
| # | Входные данные | Выходные данные |
|
1 |
3 3
0 1 1 1 0 1 1 0 0 |
1 2 0 |
|
2 |
6 5
0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 |
2 2 1 1 0 -1 |
|
3 |
3 1
0 0 0 0 0 1 1 1 0 |
0 -1 -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 |
#include <iostream> #include <queue> using namespace std; int graph[1001][1001], d[1001]; queue <int> q; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, x, v; cin >> n >> x; x--; 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++) { d[i] = -1; } q.push(x); d[x] = 0; while (!q.empty()) { v = q.front(); q.pop(); for (int i = 0; i < n; i++) { if (d[i] == -1 && graph[v][i]) { q.push(i); d[i] = d[v] + 1; } } } for(int i = 0; i < n; i ++) { cout << d[i] << " "; } return 0; } |
Решение
Данную задачу будем решать поиском в ширину. Сам граф будем хранить в двумерном массиве graph[][], в массиве d[] будем хранить кратчайшее расстояние между заданной вершиной и $i$-ой. В очереди queue <int> q будем хранить обрабатываемые вершины. В самом начале там будет хранится только наша исходная вершина, затем пока в очереди хранятся какие-либо вершины достаем верхнюю и смотрим ребра, выходящие из нее, если ранее вершины не были задействованными, то помещаем в конец очереди. Очередь опустеет, когда будут просмотрены все вершины, в которые можно попасть из исходной $x$. Сложность алгоритма $O(n)$.