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