1 / 1 / 0
Регистрация: 09.12.2009
Сообщений: 30
|
||||||
1 | ||||||
Алгоритм Форда - Беллмана29.02.2012, 18:57. Показов 24398. Ответов 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
Алгоритм форда беллмана |
![]() 4726 / 2547 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
01.03.2012, 03:16 | 2 | |||||
все правильно. Остается надеется, что:
словосочетание "отрицательного веса" относится только к дугам. А вообще, условие немного кривоватое: Правильно будет:
1
|
93 / 69 / 22
Регистрация: 17.10.2011
Сообщений: 235
|
|
01.03.2012, 09:19 | 3 |
из википедии по теории графов:
Расстояние между вершинами - длина кратчайшей цепи (в орграфе пути), соединяющей заданные вершины. Путь в орграфе — это последовательность вершин v1, v2, …, vn, для которой существуют дуги v1 → v2, v2 → v3, …, vn-1 → vn. Говорят, что этот путь начинается в вершине v1, проходит через вершины v2, v3, …, vn-1, и заканчивается в вершине vn.
0
|
1 / 1 / 0
Регистрация: 09.12.2009
Сообщений: 30
|
|
01.03.2012, 09:56 [ТС] | 4 |
0
|
0 / 0 / 1
Регистрация: 19.09.2014
Сообщений: 19
|
|
17.11.2014, 19:06 | 5 |
Можете обьяснить, что у Вас делает функция solve? (просто со структурами не представляю как пояснить это)
0
|
3 / 1 / 2
Регистрация: 18.05.2016
Сообщений: 14
|
||||||
22.05.2016, 04:22 | 6 | |||||
подскажите пожалуйста что делает строка вторая строка в теле цикла (t.a--; t.b--
![]()
0
|
2 / 2 / 0
Регистрация: 27.02.2022
Сообщений: 18
|
|
13.12.2022, 12:54 | 7 |
потому что вершины вводятся с 1, а нумерация в плюсах идет с 0
все банально
0
|
13.12.2022, 12:54 | |
Помогаю со студенческими работами здесь
7
Как реализовать Алгоритм Беллмана-Форда со смежной матрицей?
Восстановление пути из алгоритма Форда-Беллмана Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |