e-olimp 4852. Кратчайшее расстояние

Задача

Дан ориентированный граф. Найдите кратчайшее расстояние от вершины 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

 

Реализация

Засчитанное решение на e-olimp.com

Код на ideone.com

Решение

Для решения данной задачи необходимо применить  алгоритм Дейкстры . А именно, мы храним в массиве текущую длину наиболее короткого пути из заданной вершины во все остальные вершины графа. Положим, что изначально длина такого пути равна бесконечности ( при реализации просто используем достаточно большое число). А длина пути из заданной вершины до самой себя равна нулю. Обозначим, что вершина может быть помечена или не помечена. Изначально все вершины являются не помеченными. Далее выбираем  вершину [latex]v[/latex] с наименьшей длиной пути до заданной вершины и помечаем ее. Тогда просматриваем все ребра, исходящие из вершины [latex]v[/latex]. Пусть эти ребра имеют вид  [latex]\left ( v,t_0 \right )[/latex]. Тогда для каждой такой вершины [latex]t_0[/latex] пытаемся найти наиболее коротки путь из заданной вершины. После чего снова выбираем еще не помеченную вершину и проделываем вышеописанный алгоритм снова до тех пор, пока не останется не помеченных вершин. Найденные расстояния и будут наименьшими.

e-olymp 982. Связность

Задача. Проверить, является ли заданный неориентированный граф связным, то есть что из любой вершины можно по рёбрам этого графа попасть в любую другую.

Входные данные

В первой строке заданы количество вершин [latex]n[/latex] и ребер [latex]m[/latex] в графе соответственно [latex](1 \leq n \leq 100, 1 \leq m \leq 10000)[/latex]. Каждая из следующих m строк содержит по два числа [latex]u_i[/latex] и [latex]v_i[/latex] [latex](1 \leq u_i, v_i \leq n);[/latex]  каждая такая строка означает, что в графе существует ребро между вершинами [latex]u_i[/latex] и [latex]v_i[/latex].

Выходные данные

Выведите «YES», если граф является связным и «NO» в противном случае.

Тесты

Тесты, взятые с e-olymp.com

Test Input Output
1 3 2
1 2
3 2
YES
2 3 1
1 3
NO

Мои тесты

Test Input Output
1 4 2
1 2
3 4
NO
2 4 5
1 2
2 1
2 4
2 4
4 2
NO
3 5 4
1 2
5 1
3 5
4 3
YES

Код программы

Алгоритм

Чтобы установить, является ли граф связным, я использовала удобный для этого алгоритм поиска в ширину. Он заключается в следующем: начиная с какой-то вершины, мы поочередно просматриваем все вершины, соседние с ней. Каждую посещенную вершину мы помечаем маркером. Затем повторяем этот процесс для каждой из соседних вершин, и так далее. Поиск будет продолжаться, пока мы не обойдем все вершины, которые можно достигнуть из данной. Если после этого в графе осталась хотя бы одна не помеченная вершина, значит из нее нельзя попасть в помеченные, то есть граф не является связным. При этом неважно, с какой вершины мы будем начинать поиск, ведь нам нужно установить сам факт, связный граф или нет.

Код программы

Засчитанное решение на сайте e-olymp.com

e-olymp 5071. Проверка на неориенитрованность

Задача. Проверка на неориенитрованность

Условие задачи

По заданной квадратной матрице [latex]n\times n[/latex]  из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.

Входные данные

Входной файл содержит число [latex]n(1\leq n\leq 100)[/latex] — размер матрицы, и затем [latex]n[/latex] строк по [latex]n[/latex] чисел, каждое из которых равно [latex]0[/latex] или [latex]1[/latex] — саму матрицу.

Выходные данные

Выведите в выходной файл YES если приведенная матрица может быть матрицей смежности простого неориентированного графа и NO в противном случае.

Также условие задачи можно посмотреть здесь.

Тестирование

Входные данные Выходные данные
1. 3
0 1 1
1 0 1
1 1 0
YES
2. 3
0 1 0
1 0 1
1 1 0
NO
3. 3
0 1 0
1 1 1
0 1 0
NO

Реализация

Алгоритм решения

Чтобы введённая матрица была матрицей смежности простого неориентированного графа, она должна, во-первых, быть симметричной, то есть элементы на соответствующих позициях должны быть равны между собой: [latex]a[i][j]=a[j][i][/latex]. Во-вторых, необходимо, чтобы элементы главной диагонали матрицы равнялись нулю. Таким образом, нам нужно проверить, выполняются ли указанные условия.
Создаём переменную f типа bool. Изначально f=true. Если при проверке на симметричность и равенство нулю главной диагонали хоть одно значение элемента матрицы не удовлетворяет условию, флаг устанавливается в «ложь» и происходит выход из цикла проверки. Это означает соответственно, что введённая матрица не является матрицей смежности неориентированного графа, — на экран выводится «NO». Если же оба условия выполняются, приведённая матрица — матрица смежности. Выводим «YES».

Подробнее о графах и матрице смежности можно прочесть, используя следующие интернет-ресурсы:

Для запроса на выполнение следует перейти по ссылке.

Ссылка на засчитанное решение на e-olymp.com.

e-olimp 4856. Кратчайший путь

Ілларіонова Марія Валеріївна
Ілларіонова Марія Валеріївна

Latest posts by Ілларіонова Марія Валеріївна (see all)

Задача e-olimp.com №4856. Ссылка на засчитанное решение.

Дан неориентированный взвешенный граф. Найти кратчайший путь между двумя данными вершинами.

Входные данные

Первая строка содержит натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex]\left(n\leq 2000, m\leq 50000 \right)[/latex] — количество вершин и рёбер графа. Вторая строка содержит натуральные числа [latex]s[/latex] и [latex]f[/latex] [latex]\left(1\leq s, f\leq n, s\neq f \right)[/latex] — номера вершин, длину пути между которыми требуется найти. Следующие [latex]m[/latex] строк содержат по три числа [latex]b_{i}[/latex], [latex]e_{i}[/latex] и [latex]w_{i}[/latex]- номера концов [latex]i[/latex]-ого ребра и его вес соответственно [latex]\left(1 \leq b_{i}, e_{i}\leq n, 0\leq w_{i}\leq 100000\right)[/latex].

Выходные данные

Первая строка должна содержать одно число — длину минимального пути между вершинами [latex]s[/latex] и [latex]f[/latex]. Во второй строке через пробел выведите вершины на кратчайшем пути из [latex]s[/latex] в [latex]f[/latex] в порядке обхода. Если путь из [latex]s[/latex] в [latex]f[/latex] не существует, выведите -1.

Код программы:

Для решения использовался алгоритм Дейкстры, подробнее в комментариях к коду.