| 1 Хабибуллозода Наджибулло Сайфуллоевич, 06 ноября 2025 г. 9:48:01 |
| Да задача легкая главная знать Нахождение отрицательного цикла в графе Решение с помощью алгоритма Флойда-Уоршелла и помог тест Омельяненко Андрій Миколайович и все ;)))
|
|
|
| 2 Балюк Иван Юрьевич, 04 ноября 2024 г. 22:52:28 |
| Пожалуйста, добавьте пример, где есть вершина в отдельной компоненте связности, и где на главной диагонали у неё стоит ноль. Убил весь день на то, чтобы просто понять, что оказывается, что даже если на главной диагонали стоит 0, кратчайший путь в виде неявной петли всё равно существует и надо выводить 1, а не 0
|
|
|
| 3 Кактус, 22 июля 2022 г. 15:12:27 |
| Бред. Если в исходной матрице нет прохода из i в i, почему в конечных он появляется?
|
|
|
| 4 Дмитриев Дмитрий Андреевич, 10 апреля 2020 г. 9:12:33 |
| 2 аккуратных запуска Флойда, с небольшой хитростью между запусками) Главное в индексах опечатки недопускать:D
|
|
|
| 5 Чопонов Данияр, 08 апреля 2020 г. 11:14:36 |
| замените на вещественные, мучался 2 недели проверял на разных чекерах. Из-за того что не учел переполнение int-ов
|
|
|
| 6 Зинов Вадим, 06 апреля 2020 г. 10:27:01 |
| Это очень странно, что вершины без петель и не в цикле неожиданно имеют путь сами в себя. Сколько я пострадал с этими единицами на диагонали...
|
|
|
| 7 Даниил, 21 августа 2016 г. 11:37:53 |
Ребят, все заходит дефолтным фордом.
Нужно только еще учитывать петли на главной диагонали.
Работает все с обычным INF = (int)1e9
Никаких сравнений с numeric_limits не нужно, даблов тем более.
|
|
|
| 8 Коната Изуми, 21 мая 2014 г. 1:13:05 |
| Здорово помучился (по собственной глупости), но таки сдал без использования Флойда и шаманства с плавающей точкой, используя один DFS.
|
|
|
| 9 Черкес Сергей Викторович, 26 августа 2013 г. 22:15:55 |
| Прочел множество коментов, и хочу сказать, что по int все проходит прекрасно. Главное подобрать правильно константу для бесконечности, но и понять, что значит "столь угодно мало". Удачи в решении!!!
|
|
|
| 10 Омельяненко Андрій Миколайович, 28 марта 2013 г. 18:09:14 |
Почему для теста
4
-1 -1 -1 -1
0 0 0 0
0 0 0 0
0 0 0 0
Ответ
4
2 2 2 2
0 1 0 0
0 0 1 0
0 0 0 1
Мы ведь можем много раз ходить из 1 в 1, а потом перейти в 2,3,4 с -maxlongint???
Именно так, поэтому и такой ответ. Поэтому из 1й вершины во все получаем сколь угодно малый путь, поэтому вся первая строка из чисел 2 и получается. А из других вершин мы не можем попасть никуда, кроме как в самих себя с кратчайшим нулевым маршрутом, поэтому на диагонали 1, а остальные 0.
|
|
|
| 11 Балакший Андрей Владимирович, 10 ноября 2011 г. 8:46:29 |
Нет, длинки нету, хоть расстояния и могут принимать очень большие по модулю значения, double хватит + ограничить каким нибудь числом:
a[i][j] = max(-inf, min(a[i][j], a[i][k] + a[k][j]));
|
|
|
| 12 Арцукевич Дмитрий Александрович, 17 августа 2011 г. 20:45:38 |
| а здесь нету случайно длинной арифметики ?
|
|
|
| 13 ПростокваШИНОмонтаж, 30 мая 2011 г. 10:45:39 |
| Пацаны, пишите double!
|
|
|
| 14 ХуС++, 28 ноября 2010 г. 20:26:19 |
какой ответ будет при
3
0 1 0
0 0 -1
0 0 0
?
1 1 1
0 1 2
0 0 1
не такой?
Не такой, поскольку у нас здесь нет циклов, то не может быть сколько угодно малого маршрута. Поэтому вашу единственную 2ку в данном случае надо заменить на 1.
|
|
|
| 15 пицца, 20 мая 2010 г. 11:01:38 |
Задачу можно было решить за один проход массива алгоритмом?
Сомневаюсь, что такое возможно.
|
|
|
| 16 Хаканай Каиго, 12 мая 2010 г. 11:09:16 |
Прошу обратить внимание, что тест
1
0
правильный ответ 1. У меня не проходило именно из не учета одного маленького условия:)
|
|
|
| 17 Щербина Никита Юриевич, 24 декабря 2009 г. 14:43:11 |
Мне все равно не очень понятно условие...какой смысл задавать вес ребра(все равно 5 или 10)?вес ребра из вершины i в j обязательно равен весу из j в i?
Вес ребра очень важен в этой задаче. у нас граф ориентированный, поэтому вес из i в j может отличаться от j в i, причем может не существовать в одном из направлений.
|
|
|
| 18 Никита, 23 декабря 2009 г. 13:52:47 |
а можно по одной дорожке ходить несколько раз?
Можно :) Интересная у вас терминология "ходить по одной дорожке несколько раз", я бы заменил на следующее "наикратчайший путь содержит многократное вхождение ребер".
|
|
|
| 19 Прищенко Богдан Олегович, 03 ноября 2009 г. 20:01:59 |
| Не знаю, хватает или нет, я себе сгенерил штук 20 тестов - так нигде больше 10 в 85ом не понадобилось. А математически анализировать, сколько может получиться, мне сейчас не охота:) У меня АС решение с 10^100.
|
|
|
| 20 Ганеев Рустам Ринатович, 13 мая 2009 г. 14:09:38 |
такой тест:
1
0
какой правильный ответ?
1
?
Да, ваш вариант правильный. Здесь существует путь, в котором 0 ребер, из 1й в 1ю вершину.
|
|
|
