Задача
Дан ориентированный граф. Найдите кратчайшее расстояние от вершины x до всех остальных вершин графа.
Входные данные
В первой строке содержатся два натуральных числа [latex]n[/latex] и [latex]x[/latex] [latex]\left ( 1\leq n\leq 1000,1\leq x\leq n \right )[/latex] — количество вершин в графе и стартовая вершина соответственно. Далее в [latex]n[/latex] строках по [latex]n[/latex] чисел — матрица смежности графа: в [latex]i[/latex]-ой строке на [latex]j[/latex]-ом месте стоит [latex]1[/latex], если вершины [latex]i[/latex] и [latex]j[/latex] соединены ребром, и [latex]0[/latex], если ребра между ними нет. На главной диагонали матрицы стоят нули.
Выходные данные
Выведите через пробел числа [latex]d_1,d_2,[/latex][latex]\ldots[/latex][latex],d_i[/latex], где [latex]d_i[/latex] равно[latex]-1[/latex], если путей между [latex]x[/latex] и [latex]i[/latex] нет, в противном случае это минимальное расстояние между [latex]x[/latex] и [latex]i[/latex].
Тесты
| Входные данные | Выходные данные |
| 3 1 0 1 0 0 0 0 0 0 0 |
0 1 -1 |
| 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 1 0 1 0 1 0 1 0 1 0 |
0 1 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 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { const int inf=4000; // задаем бесконечность int n, start_position, x; // n-количество вершин,х используем для приема матрицы смежности cin>>n>>start_position; start_position--; // в условии счет начинается с единицы, а в программе с нуля vector <int> verges [1001]; //задаем массив векторов, где i-ый вектор содержит в себе номера вершин в которые можно попасть с i-ой вершины for (int i=0; i<n; i++){ for(int j=0; j<n; j++){ cin>>x; if (x==1){ verges[i].push_back(j); } } } bool *used = new bool [n]; for (int i=0; i<n; i++){ used[i]=false; } int *distances = new int [n]; //задаем массив расстояний, где i-ый элемент - это расстояние от исходной вершины до i-ой for (int i=0; i<n; i++){ distances[i]=inf; } distances[start_position] = 0; for (int i=0; i<n; i++){ //ищем вершину с наименьшей длиной пути до заданной вершины int minimum=inf; int position = 0; for (int j=0; j<n; j++){ if (distances[j]<minimum && !used[j]){ minimum=distances[j]; position=j; } } used[position]=true; //запоминаем, что применили алгоритм для вершины for (int i=0; i<verges[position].size(); i++){ // применяем алгоритм Дейкстры distances[verges[position][i]] = min(distances[verges[position][i]], (distances[position]+1)); } } for (int i=0; i<n; i++) { cout<<((distances[i]==inf)?-1:distances[i])<<" "; } return 0; } |
Засчитанное решение на e-olimp.com
Код на ideone.com
Решение
Для решения данной задачи необходимо применить алгоритм Дейкстры . А именно, мы храним в массиве текущую длину наиболее короткого пути из заданной вершины во все остальные вершины графа. Положим, что изначально длина такого пути равна бесконечности ( при реализации просто используем достаточно большое число). А длина пути из заданной вершины до самой себя равна нулю. Обозначим, что вершина может быть помечена или не помечена. Изначально все вершины являются не помеченными. Далее выбираем вершину [latex]v[/latex] с наименьшей длиной пути до заданной вершины и помечаем ее. Тогда просматриваем все ребра, исходящие из вершины [latex]v[/latex]. Пусть эти ребра имеют вид [latex]\left ( v,t_0 \right )[/latex]. Тогда для каждой такой вершины [latex]t_0[/latex] пытаемся найти наиболее коротки путь из заданной вершины. После чего снова выбираем еще не помеченную вершину и проделываем вышеописанный алгоритм снова до тех пор, пока не останется не помеченных вершин. Найденные расстояния и будут наименьшими.
Мне кажется, что вполне достаточно было бы простого поиска в глубину