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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Квадро-деревья (Q-деревья). Вывод данных в порядке следования первого ключа. http://www.cyberforum.ru/cpp-beginners/thread376375.html
Здравствуйте, уважаемые программисты всея форума! Доброго вам времени суток! Возник у меня вопрос =) Пусть у нас есть Q-дерево, причем данные могут содержаться в ЛЮБОМ узле этого дерева. И...
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{ // разрешающая способность...
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
1058 / 577 / 24
Регистрация: 03.12.2009
Сообщений: 1,255

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

01.11.2011, 22:13. Просмотров 1766. Ответов 5
Метки (Все метки)

Здравствуйте!

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

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

Сама задача

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

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

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

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

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

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;
}

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

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


Спасибо!!
0
Миниатюры
АТД Графы. Поиск суммы расстояний между городами.  
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru