![]() 1 / 1 / 0
Регистрация: 09.12.2009
Сообщений: 30
|
||||||
Алгоритм Форда - Беллмана29.02.2012, 18:57. Показов 26456. Ответов 6
Метки нет Все метки)
(
Помогите пожалуйста понять что не так у меня.
ограничение времени на тест: 1 сек. ограничение памяти на тест: 32768 KB. ввод: standard вывод: standard Дан взвешенный ориентированный граф из N вершин и M дуг. В графе могут быть петли и/или дуги отрицательного веса. Известно, что нет циклов отрицательного веса. Требуется найти расстояние от первой вершины до всех остальных. Между любой парой вершин не может быть более одной дуги в одном направлении. Входные данные В первой строке записаны N и M (2<=N<=1000, 0<=M<=10000). Дальше идет M строк с тройками целых чисел X, Y, L - дуга из X в Y имеет вес L (1<=X,Y<=N, -1000<=L<=1000). Выходные данные Выведите N-1 строку. В строке с номером i должно содержаться расстояние от первой вершины до вершины с номером (i+1). Если до данной вершины дойти нельзя, то в соответствующей строчке необходимо вывести "NO". Пример Ввод 6 7 1 2 -3 1 1 8 2 3 1 1 3 1 3 4 -2 3 1 2 4 6 10 Вывод -3 -2 -4 NO 6
Не могу понять сколько раз можно проходить через петлю, ведь если она отрицательная, то это все равно что и отрицательный цикл
0
|
29.02.2012, 18:57 | |
Ответы с готовыми решениями:
6
|
![]() ![]() 4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||||||
01.03.2012, 03:16 | ||||||||||
А вообще, условие немного кривоватое:
1
|
93 / 69 / 22
Регистрация: 17.10.2011
Сообщений: 235
|
|
01.03.2012, 09:19 | |
из википедии по теории графов:
Расстояние между вершинами - длина кратчайшей цепи (в орграфе пути), соединяющей заданные вершины. Путь в орграфе — это последовательность вершин v1, v2, …, vn, для которой существуют дуги v1 → v2, v2 → v3, …, vn-1 → vn. Говорят, что этот путь начинается в вершине v1, проходит через вершины v2, v3, …, vn-1, и заканчивается в вершине vn.
0
|
3 / 1 / 2
Регистрация: 18.05.2016
Сообщений: 14
|
||||||
22.05.2016, 04:22 | ||||||
подскажите пожалуйста что делает строка вторая строка в теле цикла (t.a--; t.b--
![]()
0
|
![]() 3 / 3 / 0
Регистрация: 27.02.2022
Сообщений: 18
|
|
13.12.2022, 12:54 | |
потому что вершины вводятся с 1, а нумерация в плюсах идет с 0
все банально
0
|
13.12.2022, 12:54 | |
Помогаю со студенческими работами здесь
7
Алгоритм форда беллмана Как реализовать Алгоритм Беллмана-Форда со смежной матрицей?
Восстановление пути из алгоритма Форда-Беллмана Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Опции темы | |
|
Новые блоги и статьи
![]() |
||||
Kanban или Scrum - что выбрать?
EggHead 27.04.2025
Kanban и Scrum — уже много лет удерживают лидирующие позиции среди гибких подходов. Руководители проектов и команды разработчиков то и дело сталкиваются с дилеммой: какой из этих двух методов выбрать. . .
|
Кастомные Middleware на C# в ASP.NET Core
UnmanagedCoder 27.04.2025
Разработка веб-приложений сегодня мало напоминает монолитное программирование прошлых лет. На смену громоздким блокам кода пришла модульная архитектура, где каждый компонент выполняет строго. . .
|
Анализ и линтинг кода JavaScript: ESLint, Prettier и JSHint
run.dev 26.04.2025
JavaScript прошёл долгий путь от простого языка для анимации веб-страниц до основы современной веб-разработки. С ростом сложности приложений, увеличением кодовых баз и масштабированием команд. . .
|
Паттерны в Python: Singleton, Factory и Observer
py-thonny 26.04.2025
Паттерны проектирования — это проверенные временем решения типовых проблем разработки программного обеспечения. Их история берёт начало с книги "Приёмы объектно-ориентированного проектирования. . . .
|
Исключения в C#: Stack Overflow, Access Violation и Out of memory
stackOverflow 26.04.2025
Исключения в C# — это не только механизм оповещения о проблемах, а целое искусство управления потоком выполнения программы в экстремальных ситуациях. Обычное исключение, например,. . .
|
Логирование в C# ASP.NET Core с помощью Serilog, ElasticSearch, Kibana
stackOverflow 25.04.2025
Помните те времена, когда для анализа проблемы приходилось подключаться к серверу, искать нужный лог-файл среди десятков других и вручную фильтровать тысячи строк в поисках ошибки? К счастью, эти дни. . .
|
Структура "железный OnKeyUp" вместо антидребезга. Полностью асинхронный счётчик.
Hrethgir 25.04.2025
Программа для симуляции схемы - Logisim Evolution
В общем какое-то время отвлёкся, так было надо, теперь когда запилю это на verilog и FPGA , досоставлю заявку в ФИПС на полезную модель - не готов. . .
|
Автоматизация Amazon Web Services (AWS) с Boto3 в Python
py-thonny 25.04.2025
Облачные вычисления стали неотъемлемой частью современной ИТ-инфраструктуры, а Amazon Web Services (AWS) занимает лидирующие позиции среди провайдеров облачных услуг. Управление многочисленными. . .
|
Apache Kafka vs RabbitMQ в микросервисной архитектуре
ArchitectMsa 25.04.2025
Современная разработка ПО всё чаще склоняется к микросервисной архитектуре — подходу, при котором приложение разбивается на множество небольших, автономных сервисов. В этой распределённой среде. . .
|
Параллельное программирование с OpenMP в C++
NullReferenced 24.04.2025
Параллельное программирование — подход к созданию программ, когда одна задача разбивается на несколько подзадач, которые могут выполняться одновременно. Оно стало необходимым навыком для. . .
|