Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Алгоритм Форда - Беллмана - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Не получается передать массив в функцию. http://www.cyberforum.ru/cpp-beginners/thread455209.html
#include <iostream> #define n 20 #define m 30 using namespace std; void switcher (int** arr, int a, int b); int main() { int arr;
C++ Как в с/с++ можно подсчитать количество символов, обработанных в единицу времени Добрый день, у меня такой вопрос: Допустим есть функция перебирающая большой текстовый файл и например подсчитывающая количество пробелов, или например заменяющая одни символы другими. Как можно во... http://www.cyberforum.ru/cpp-beginners/thread455205.html
Просканировать строку, и вернуть слово, если ASCII код каждой буквы этого слова четный C++
написать функцию которая сканирует строку и возвращает слово если ASCII код каждой буквы этого слова четный.Пользоваться арифмитическими операциями нельзя. Напишите пожалуйста если кто знает....
Добавление в исключения антивируса C++
Итак, есть программа, работающая с файлами (довольно активно - чтение/запись/шифрование), отправляющая их по инету в центр обработки данных (сайчас это сервер у меня на кухне - вот так работает 152...
C++ Создать массив, каждый элемент которого является суммой строки исходной матрицы http://www.cyberforum.ru/cpp-beginners/thread455154.html
Доброго времени суток. Помогите пожалуйста с кодом. Ниже часть проги, которая создает массив2, каждый элемент которого равен сумме строки массива1. Почему в цикле if a выводит какое-то левое...
C++ Динамическое создание объекта класса Примерно что должно получится: #include <iostream> #include <string> using namespace std; class student { string name; public: void y () подробнее

Показать сообщение отдельно
Niсe
1 / 1 / 0
Регистрация: 09.12.2009
Сообщений: 30

Алгоритм Форда - Беллмана - C++

29.02.2012, 18:57. Просмотров 7029. Ответов 5
Метки (Все метки)

Помогите пожалуйста понять что не так у меня.
ограничение времени на тест: 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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cmath>
using namespace std;
const int inf = 1555555555;
int main()
{
    int n, m, x, y, l;
    cin>>n>>m;
    int * d=  new int[n];
    for(int i = 0; i < n; i++)
        d[i]=inf;
    int ** w = new int *[n];
    for(int i = 0; i < n; i++)
        w[i] = new int [n];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
        {
            if(i==j)w[i][j]=0;
            else w[i][j]=inf;
        }
    for(int i = 0; i < m; i++)
    {
        cin>>x>>y>>l;
        w[x-1][y-1]= min(w[x-1][y-1], l);
    }
    d[0]=0;
    for(int k = 0; k < n; k++)
    {   
        bool usl = false;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(w[i][j]<inf/2)               
                    if(d[j]>d[i]+w[i][j])
                    {
                        d[j]=d[i]+w[i][j];
                        usl = true;
                    }
            }
            if(!usl) break;
        }
 
    }
    for(int i = 1; i < n-1; i++)
        if(d[i]<inf/2)cout<<d[i]<<endl;
        else cout<<"NO"<<endl;
        if(d[n-1]<inf/2)cout<<d[n-1]<<endl;
            else cout<<"NO"<<endl;
    for(int i = 0; i < n; i++)
    delete[] w[i];
    delete[] w;
    delete[] d;
    return 0;
}
Добавлено через 2 часа 52 минуты
Не могу понять сколько раз можно проходить через петлю, ведь если она отрицательная, то это все равно что и отрицательный цикл
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru