| 1 Неизвестный, 07 февраля 2026 г. 15:34:16 |
| простой kfc с вкусными крылышками
|
|
|
| 2 Неизвестный, 18 ноября 2025 г. 15:23:19 |
| У кого проблемы это задача тупо BFS.Массив в котором вы считаете дистанции сначала все значении в его позициях должны равны -1 если хотите решить задачу по простому
|
|
|
| 3 Кенджаев Мухаммадали, 20 сентября 2025 г. 12:39:16 |
| from collections import deque n = int(input()) r = {i:[] for i in range(1, n + 1)} a = [] for i in range(n): a += [list(map(int, input().split()))] for i in range(n): for j in range(n): if a[i][j] == 1: r[i + 1] += [j + 1] x, y = map(int, input().split()) o = deque() o.append(x) v = {i:0 for i in range(1, n + 1)} v[x] = -1 while o: p = o.pop() if p == y: break for i in r[p]: if v[i] == 0: v[i] = p o.append(i) l = -1 t = y while t > 0: t = v[t] l += 1 if l == 0 and x != y: l = -1 if x != y: print(l) else: print(-1) НЕ ПРОХОДИТЬ ТЕСТ 5
|
|
|
| 4 Арестович Егор Викторович, 02 апреля 2025 г. 19:09:49 |
| Какой 4 тест? Что за бред?
|
|
|
| 5 ЧТо, 15 августа 2023 г. 11:51:44 |
| BFS обход в ширину и всё
|
|
|
| 6 Шмойлов Артём Алексеевич, 20 марта 2023 г. 18:40:38 |
| Я решил задачу где-то за 20 минут, но из-за -1 я решал 3 часа, думая что - это тире))).
|
|
|
| 7 Рудь Илья Викторович, 28 января 2023 г. 20:34:03 |
| Решил Дейкстрой
|
|
|
| 8 Лагман, 16 февраля 2021 г. 9:33:50 |
| я так понял в графе есть петли
|
|
|
| 9 Лавренович Алексей Евгеньевич, 26 января 2021 г. 2:33:17 |
| Решил с помощью возведения в степень матрицы, где степень как раз длина пути. Вроде работает сносно
|
|
|
| 10 Попов Матвей Павлович, 21 декабря 2020 г. 13:31:21 |
| Где можно найти порядочный гайд для чайников на этот ваш Волновой алгоритм, никак не могу найти?
|
|
|
| 11 Абдувохидов Эльдар Абдурахмонович, 01 ноября 2020 г. 17:25:51 |
| Я оказывается не дочитал, и там если пути нет, то выводится -1.
|
|
|
| 12 Зинов Вадим, 26 ноября 2019 г. 20:35:24 |
| Скопировал флода, АС. Один вопрос зачем делать тест из вершины в нее же? Судя по матрице смежности такого перехода по умолчанию нет =(
|
|
|
| 13 Захаров Константин Леонидович, 08 февраля 2013 г. 23:57:01 |
Бфс очень хорошая штука. Есть такая штука очередь в С++ (которую кстати и паскаль позволяет реализовать на рас-два), можно пользуясь ею очень неплохо реализовать этот самый бфс. Сохраняем матрицу смежности. Записываем в массивчике used для первой вершины значение 1, добавляем ее в очередь. Начинаем цикл while пока очередь не пуста. Вытаскиваем из очереди элемент. И для каждого его непосещенного соседа (used[сосед] = 0) в цикле делаем так - закинуть его в очередь, в массив used прописать значение used[текущий] + 1. Потом когда очередь опустеет - цикл while кончится и останется проверить, приходили ли мы когда-нибудь во вторую вершину (used[second] = 0, значит не были). Если были, то выводим used[second] - 1. Можно еще в самом цикле while прописать условие, что если вытащили элемент из очереди, а он это искомый second, то break; но худший тест все равно остается возможен, так что думаю такие проверки стоит добавлять только при очень яростной борьбе за время.
Спасибо, надеюсь, что это поможет тем, кто не знает ничего о волновом алгоритме или поиске в ширину.
|
|
|
| 14 Филипп Кофман Олегович, 16 августа 2012 г. 4:40:57 |
| С первого раза В-) Задача простая. 1) Нам нужно для каждой вершины хранить так сказать длину пути из стартовой вершины. 2)Для стартовой вершины этот путь равен 0 для всех кто к ней касается 1 и т. д. 3) Нам нужно заполнить эти значения для каждой вершины . 4) Заведем очередь где 1 элемент старт. Обрабатываем очередь пока она не пуста. Первая вершина в очередь нами обрабатывается так находим все вершины которые с ней связаны и не были ещё просмотрены и запиливаються в очередь в конец а номерам их длин мы присваиваем значение длины первого элемента в очереди +1.
|
|
|
| 15 Тест Тест Тест, 30 октября 2011 г. 21:59:03 |
Имхо: гораздо легче Дейкстрой сдать. Здесь мучение это БФС как раз.
БФС проще Дейкстры.
|
|
|
| 16 Каменко&Барышев, 01 апреля 2011 г. 18:52:55 |
| когда начальная вершина с конечной совпадают то надо выводить 0
|
|
|
| 17 Мас Мих В, 18 января 2010 г. 22:18:55 |
| Простой bfs
|
|
|
| 18 Рубаненко Роман Сергеевич, 06 сентября 2009 г. 21:00:10 |
А дейкстра тут не пашет???!!!
Пашет, но зачем так мучиться, ведь длины ребер одинаковые (равны единице) и волновой алгоритм здесь вполне приемлем.
|
|
|
| 19 Белкин Алексей Александрович, 28 мая 2009 г. 8:49:31 |
а обходом в глубину будет работать? Просто интересно: из-за чего у меня TimeLimit.
нет, тут все-таки лучше в ширину, волновым алгоритмом.
|
|
|
| 20 Диханов Ануар Кайратович, 25 марта 2009 г. 14:06:06 |
Обьясните пожалуйста эту задачу подробнее.
Рекомендую в интернете поискать материал по теории графов. Графы очень часто используются в олимпиадных задачах, такие знания вам пригодятся. В двух словах мне сложно тут объяснить суть.
|
|
|
