Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1
  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 ))))
плииз, поправьте условие
     Горбиков выше совершенно верно написал. Замечу, что во входных данных числа все целые! Так что если бы я в формулировке задачи это упомянул, то возможно, вы ее так и не решили бы :)
 1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru