| 1 Хабибуллозода Наджибулло Сайфуллоевич, 16 октября 2025 г. 7:25:08 |
| Спасибо Кактусу за хороший тест :)
|
|
|
| 2 Лоскутов Прохор Александрович, 24 июня 2023 г. 16:06:04 |
| Задача невкусная
|
|
|
| 3 Билалов Тимур, 15 июня 2023 г. 16:34:40 |
| Значица идея проста, делаем стандартного Беллмана, только для максимума, проверяем если у нас минус бесконечность в d[n - 1], если нет , то проверяем на циклы dfs, запоминаем конфигурацию ответа, делаем релаксацию, то есть один проход Беллманом, если в значениях будут отличаться значения с теми, что мы запомнили до Беллмана, то проверяем можно ли отсюда добежать до конца, если да, то цикл может накрутить ответ. Один из тестов это (3 3 1 2 -100 2 2 100 1 3 -1000) -> -1000
|
|
|
| 4 Кактус, 22 июля 2022 г. 18:21:08 |
| 13 тест подобен этому: 3 4 1 3 10000 1 2 -10000 2 2 1 2 3 -10000 Правильный ответ: ":)"
|
|
|
| 5 Кактус, 22 июля 2022 г. 18:06:13 |
| По идее если мы можем получить бесконечное кол-во знаний, то максимум за дополнительные N итераций значение для последней комнаты должно обновиться. Я физически не могу заснуть от того что не понимаю, почему это не сработало в этой задаче.
|
|
|
| 6 Исмоилов Исфандиёр, 25 марта 2022 г. 21:27:58 |
| Скажите пожалуйста, что нужно выводить при тесте 2 2 1 2 -2 2 1 -4
|
|
|
| 7 Мисюкевич Илья Александрович, 30 декабря 2021 г. 15:22:43 |
| Что нужно выводить на тест 1 1 1 1 4? И на тест 1 1 1 1 -4?
|
|
|
| 8 Рощупкин Дмитрий Сергеевич, 08 октября 2021 г. 15:08:56 |
| Можно 13 тест узнать пожалуйста?
|
|
|
| 9 Я ВОР АУЕ КСТА, 13 сентября 2020 г. 1:07:02 |
| Гоооспааааадиии, я в шооооооке дееевочки... Из-за этой задачи у меня теперь неприязнь к смайликам, Беллману и Форду...
|
|
|
| 10 Зинов Вадим, 09 июля 2020 г. 21:50:20 |
| Ура! Зашло, я не окончательно тупой). Что странно - была предпроверка на связность графа, решение работало 0,406 с, убрал бесполезную по сути предпроверку - 0,436с. Почему время увеличилось, а не уменьшилось, очень интересно). Спасибо за такие интересные задачи, и удобную систему для их решения.
|
|
|
| 11 Тер-Саркисов Богдан Олегович, 07 августа 2019 г. 15:13:07 |
| 10 тест не соответствует входным данным, так как в нём m = 0.
|
|
|
| 12 Шубников Кирилл Сергеевич, 17 марта 2019 г. 22:43:10 |
Это такая поджара почему тл 1 секунда ??!! Когда появился новый класс задач (Запихай) ?
Вероятно Ваш алгоритм неоптимален. Посмотрите в раздел "Лучшие попытки". Там на C++ есть и 0.186 секунды время работы.
|
|
|
| 13 Винк В В, 03 апреля 2018 г. 14:48:11 |
| Есть контрпример: 9 10 1 2 1 2 3 1 3 4 0 4 5 0 5 3 1 4 9 0 2 6 0 8 6 1 6 7 0 7 8 0 Я отправил 2 решения. Первое не прошло, но на этот тест даёт правильный ответ. Второе - всё наоборот. Если в тесте № 20 такой же рисунок лабиринта, то ...
|
|
|
| 14 Денис Розимовский, 14 июня 2015 г. 16:49:33 |
Эта задача из самых глубин ада.
Вот о чем нужно подумать.
-Если есть цикл - посмотреть, если ДО вершин цикла можно дойти с 1 и если ИЗ вершин цикла можно дойти до N. (Тут можно справиться с помощью BFS)
-Можно ли вообще дойти с 1 до N (Обычный Форд-Беллман тут не особо помог).
-Ну и потом можно уже пускать алгоритм.
|
|
|
| 15 Игнатов Олег Владимирович, 03 апреля 2015 г. 11:30:17 |
Какой здесь будет ответ?
5 5
1 2 5
2 4 5
4 5 5
3 3 5
2 3 5
|
|
|
| 16 Гатин Марат Ильхамович, 18 июля 2014 г. 13:56:16 |
Добавьте тест
4 4
1 2 7
1 3 5
3 2 8
2 4 1
|
|
|
| 17 Изобова Мария, 03 ноября 2012 г. 20:37:25 |
И второй вопрос если можно:
что должна выводить программа на тест:
3 3
1 2 2
2 3 3
3 1 4
:)
|
|
|
| 18 Журавлев Даниил Юрьевич, 23 января 2012 г. 17:27:48 |
| Как не извращался с поиском в ширину\глубину, дейкстрой, списками смежности все-равно фигня. Эх, придется смотреть Форда-Беллмана =)
|
|
|
| 19 Балакший Андрей Владимирович, 08 ноября 2011 г. 12:09:52 |
Нужно делать Форда-Беллмана для n, всем значениям цикла присваивая -inf, после этого опять Форда-Белммана для n + 1, а потом сравниваем d[n] до n - 1 итераций, и новый d[n] после n + 1.
Если они одинаковые, то цикл, даже если он есть в графе, нас не касается.
|
|
|
| 20 Селезнёв Анатолий Игревич, 20 апреля 2011 г. 18:28:17 |
| Хорошая задача и красиво решается. Кстати, вместо того, чтобы инвертировать вес ребер, можно "инвертировать" процедуру релаксации. Тогда Форд-Беллман будет сразу находить "наибольший" путь и определять наличие цикла положительного веса)
|
|
|
