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