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

1/12/2025, 6:37:10 PM 

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


 
[Вернуться к задаче]   1 2
  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) допускаются графы с петлями или по-другому псевдографы, т.е. графы у которых дуга ненулевого веса может начинаться и заканчиваться в одной и той же вершине. Если это так, то словосочетания "ориентированный взвешенный граф" недостаточно, нужно хотябы "ориентированный взвешенный псевдограф".
     Псевдограф является графом. Но если писать псевдограф, то прийдется все тесты вероятно делать с петлями :) Так что все нормально.
 1 2

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

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