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

АТД Графы. Поиск суммы расстояний между городами. - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Квадро-деревья (Q-деревья). Вывод данных в порядке следования первого ключа. http://www.cyberforum.ru/cpp-beginners/thread376375.html
Здравствуйте, уважаемые программисты всея форума! Доброго вам времени суток! Возник у меня вопрос =) Пусть у нас есть Q-дерево, причем данные могут содержаться в ЛЮБОМ узле этого дерева. И нам нужно вывести все данные этого дерева в порядке следования первого ключа (пусть для определенности это будет координата X). Честно говоря, в голове не возникает никакой мысли по поводу алгоритма...
C++ Задача по Visual C++ произведение. Дано натуральное число N. Вычислить произведение: (1+1/1^2)*(1+1/2^2)...(1+1/N^2). Картинку приложил, качество не ахти. http://www.cyberforum.ru/cpp-beginners/thread376373.html
Помогите, пожалуйста, с программой по переносу данных из файла txt в структуру C++
Помогите, пожалуйста, как написать программу, которая читает данные о ноутбуках из файла note.txt в структуру вида: Struct NOTEBOOK{ struct disp_res{ // разрешающая способность дисплея int x; // по горизонтали int у; // по вертикали }; int f; // частота регенерации float d; // размер диагонали дисплея int price; ...
C++ вопрос функции.
Начал изучать программирование по книге Рейсдорф К. Хендерсон К.- Borland C++ Builder. Освой самостоятельно... . Упражнение на 1 день учебы застало меня в расплох. Хоть убейте не могу решить, нужна помощь!!! Задание: Написать консольное приложение, которое вызвает функцию для вывода на экран текста "ХХХ". ЗЫ. стоит ли учить С++ по этой книге или же есть что-то получше в электронном варианте.
C++ Вывод текста\картинки поверх всех окон. http://www.cyberforum.ru/cpp-beginners/thread376340.html
Подскажите, как реализовать вывод текста\картинки поверх всех окон?
C++ Преобразовать массив по правилу 14. Создать массив Y из n вещественных чисел. Преобразовать его по следующему правилу: Y = max { Y, ,…,Y }, где i=1, 2,…, n. В преобразованном массиве найти такие i и j, что сумма Y+Y+ … + Y будет максимальной. Дополнительный массив использовать нельзя! Нужно срочно... Заранее спасибо.. подробнее

Показать сообщение отдельно
Infinity3000
 Аватар для Infinity3000
1057 / 576 / 24
Регистрация: 03.12.2009
Сообщений: 1,255
01.11.2011, 22:13     АТД Графы. Поиск суммы расстояний между городами.
Здравствуйте!

Нужна помощь!

Всем известная задача и в сети конечно много разнообразных тем! но не одна из них не доведена до логического завершения!!!

Сама задача

Задана система двусторонних дорог, где для любой пары городов есть соединяющий их путь. Найти город с минимальной суммой расстояний до остальных городов. Путь между двумя городами в две стороны может быть разным.

Я так понимаю нужно от каждого города находит расстояния до остальных городов и суммировать их, и сумму заносить в массив, потом с другим городом точно так и так далее!!

Потом найти минимальный элемент в массиве и его позицию, где позиция и есть искомый город!

Возможно я ошибаюсь!!

На данный момент я загружаю матрицу смежности из файла и по ней строю список инцидентности которая показывает с какого города в какой можно доехать!! (опирался на одну из тем этого форума)
осталось найти сумму расстояний до городов и из них минимальный!

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <iostream>
 
using namespace std;
 
struct row
{
        int num;
        row *next,*colum;
};
 
int outmas(int n, int **mas)
{
        int i,j;
        cout<<'№'<<' ';
        for(i=1; i<=n; ++i)
                cout << i <<' ';
        cout<<endl;
 
        for(i=0; i<n; ++i)
        {
                cout << i+1 <<' ';
                for(j=0; j < n; ++j )
                        cout<<mas[i][j] <<' ';
                cout<<endl;
        }
        return 0;
}
 
row *convert(int **mas, int n, row *top)
{
        int i,j;
        row *p,*t,*c;
        p = new row;
        p->num = 1;
        p->next = NULL;
        p->colum = NULL;
        top = p;
        for(i = 2; i <= n; ++i)
        {
                t = new row;
                t->num = i;
                t->next = NULL;
                t->colum = NULL;
                p->next = t;
                p = t;
        }
        t = top;
        p = top;
        for(i = 0; i < n; ++i)
        {
                {
                        for(j=0;j<n;++j)
                                if(mas[i][j]==1)
                                {
                                        c=new row;
                                        c->num=j+1;
                                        c->next=NULL;
                                        c->colum=NULL;
                                        p->colum=c;
                                        p=c;
                                }
                                t=t->next;
                                p=t;
                }
        }
        return top;
}
 
int outspis(row *top)
{
        row *p,*t;
        p=top;
        t=p->colum;
        while(p)
        {
                cout<<p->num<<"\t---->\t";
                while(t)
                {
                        cout<<t->num<<'\t';
                        t=t->colum;
                }
                p = p->next;
                if(p)
                        t = p->colum;
                cout<<endl;
        }
        return 0;
}
 
int main()
{
        setlocale(LC_ALL,"Rus");
 
        FILE *in = fopen("in.txt","r");
       
        int i, j, n, **mas;
        
        row *top = NULL;
 
        fscanf(in,"%d",&n);
 
        mas = new int *[n];
       
        for(i = 0; i < n; ++i)
        {
                mas[i] = new int [n];
                
                for(j = 0;  j < n; ++j)
                        fscanf(in,"%d",&mas[i][j]);
        }
 
        outmas(n,mas);
 
        top = convert(mas,n,top);
        
        cout << "\nСписок инцидентности:\n"<<endl<<"Города\t---->\tКуда можно поехать\n"<<endl;
        
        outspis(top);
        
        system("PAUSE >> null");
        delete []mas;
        fclose(in);
        return 0;
}

возможно такой ход решения не правильный!

Если есть у вас уже готовые алгоритмы решения, скиньте пожалуйста! исключительно для самообучения, не каких корыстных целей!


Спасибо!!
Миниатюры
АТД Графы. Поиск суммы расстояний между городами.  
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 22:02. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru