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

Решение задачи на графы. Country Roads - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ С++ и Java http://www.cyberforum.ru/cpp-beginners/thread829353.html
Сильно отличается C++ от Java?
C++ Массив структур, таблица, память Здравствуйте, начну с того что не знал как назвать тему, назвал по проблемам. Дали задание создать Справочник, и организовать его как очередь. Начал делать как связный список: struct point { // информация (переменные справочника) point *next; } *head, *last; Сделал, все отлично работает. Но когда пришлось добавлять такие функции как: http://www.cyberforum.ru/cpp-beginners/thread829346.html
Идентификатор не определен C++
#include<iostream.h> #include<conio.h> #include<stdio.h> int voidmain() { int i,j,r; Long int b1,b2,S,a; for(a=1; a<5; a++) for(a=1; a<=9; a++) for(a=1; a<=9; a++)
C++ Массивы. Отображать количество дней в введенном месяце
Пожалуйста помогите с программой с использованием массивов. Нужна создать программу, которая будет спрашивать пользователя вводить номер месяца, после чего программа должна отображать количество дней в этом месяце. Нужно использовать массивы и циклы, а также, если введенный пользователем номер месяца неправильный, то программа должна выводить сообщение об ошибке! Я тут немножко поработал, но...
C++ Задача на строки, с объектом класса string http://www.cyberforum.ru/cpp-beginners/thread829324.html
Дано осмысленное текстовое сообщение, разделенное пробелами и знаками препинания, в конце ставится точка. Поменять слова в сообщении по принципу: первое со вторым, третье с четвертым и т. д. Строки для меня больная тема, но насколько я понял нужно искать первые два слова, они будут записываться в переменные slovo1 и slovo2, а выводить на экран нужно: slovo2 slovo1, и искать дальше. Написать...
C++ Вычислить приближенное значение бесконечной суммы Задача 24 Вычислить приближенное значение бесконечной суммы Нужное приближение считается полученным, если абсолютное значение последнего слагаемого, вошедшего в сумму, оказалось меньше данного положительного. 1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+... подробнее

Показать сообщение отдельно
GogenMarat
Сообщений: n/a
05.04.2013, 22:47     Решение задачи на графы. Country Roads
Добрый вечер. Писал я тут решение на следующую задачу с сайта http://lightoj.com/volume_showproblem.php?problem=1002

I am going to my home. There are many cities and many bi-directional roads between them. The cities are numbered from 0 to n-1 and each road has a cost. There are m roads. You are given the number of my city t where I belong. Now from each city you have to find the minimum cost to go to my city. The cost is defined by the cost of the maximum road you have used to go to my city.

Input
Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case starts with a blank line and two integers n (1 ≤ n ≤ 500) and m (0 ≤ m ≤ 16000). The next m lines, each will contain three integers u, v, w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 20000) indicating that there is a road between u and v with cost w. Then there will be a single integer t (0 ≤ t < n). There can be multiple roads between two cities.

Output
For each case, print the case number first. Then for all the cities (from 0 to n-1) you have to print the cost. If there is no such path, print 'Impossible'.

Решение вроде как вышло и работает на всех случаях, но есть одна проблема. Сайт не принимает мое решение из за того, что я израсходовал все ресурсы(32 мб). При этом я никак не пойму, где у меня остается невысвобожденой память. Прошу помочь мне, спасибо)
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
#include <cstdio>
#include <queue>
#include<cstring>
#include<cstdlib>
#include<conio.h>
using namespace std;
 
 
 
typedef pair<int,int> tc;       //numberTown_cost
/*
линейный список для создания массива смежности
*/
class E{
public:
    tc info;
    E *next;
    E(){
        info.first=NULL;
        info.second=NULL;
        next=NULL;
    }
    E(int town,int cost){
        info.first=town;
        info.second=cost;
        next=NULL;
    }
 
};
 
/*
Обычная функция добавления элемента в линейный список.
*/
void add(E *&p,int town,int cost){
    if(p->info.first==0&&p->info.second==0){
        p->info.first=town;
        p->info.second=cost;
        return;
    }
    E *q=new E(town,cost);
    q->next=p;
    p=q;
}
/*
Класс графа. Содержит конструкторы и важные функции. Также содержит для нашей главной задачи.
*/
class Graph{
    int nu;         //кол-во городов
    E * *mass;      //массив линейных списков
public:
    Graph();        //создание пустого графа
    void addEdge(int first,int second, int cost);       //добавление ребра между городами и его цены
    void craftGraph(int n,int m);       //полное создание графа по нашим входным данным, зная изначально лишь кол-во городов и кол-во дорог
    void CountryRoads(int town);     //главная функция для решения нашей задачи
    void DelGraph();
};
/*
обычный пустой конструктор
*/
Graph::Graph(){
    nu=0;
    mass=NULL;
}
 
/*
Полное создание графа по нашим входным данным, зная изначально лишь кол-во городов и кол-во дорог.
*/
void Graph::craftGraph(int n,int m){
    nu=n;       //кол-во городов в нашем графе
    mass = new E* [n];      //массив, размерностью равный кол-ву городов. будет содержать пустые линейные списки
    for(int i=0;i<n;i++){
        mass[i]=new E();        //вот здесь пустой конструктор линейных списков. нам нечего добавлять пока что, но объявить линейные списки надо
    }
    int first,second;       //входные данные: первый и второй город
    int cost;               //цена дороги между ними
    for(int i=0;i<m;i++){
        scanf( "%d%d%d", &first, &second, &cost);           //считывание данных с input.txt
        addEdge(first,second,cost);     //доверимся функции создания ребра графа с ценой
    }
}
/*
добавление ребра графа с указанной ценой.
*/
void Graph::addEdge(int first, int second, int cost){
    add(mass[first],second,cost);      //ничего сложного.добавляем второй город с ценой дороги в линейный список первого города
    add(mass[second],first,cost);      //первый город с ценой дороги в линейный список второго города. и сможешь проезжать в обе стороны
}
 
/*
чтобы потом меньше писать. нахождение большего числа из двух заданных.
*/
int max(int a,int b){
    if(a<b){
        return b;
    }else{
        return a;
    }
}
 
/*
из за неэффективности библиотечной пары ввожу свою пару.
*/
struct reg{
    tc first;       //первый элемент
    bool *second;       //второй элемент. это булевый массив. нужен будет для проверки визитов на каждом возможном пути. причем для каждого пути свой массив визитов
    reg(int a,int b,bool *y,int n){     //конструктор два. а и b это части типа пары tc. y-массив, который будем копировать в нашу перменную типа reg. n-его будущие размеры
        first.first=a;
        first.second=b;
        second=new bool[n];
        for(int i=0;i<n;i++){
            second[i]=y[i];
        }
    }
};
 
/*
цикл для работы нашей функции заданное кол-во раз с разными входными данными
*/
void For(int h){
    Graph p;
    for(int i=1;i<=h;i++){
        int n,m;
        scanf( "%d%d", &n, &m);
        p.craftGraph(n,m);
        int Town;
        scanf( "%d", &Town);
        printf( "Case %d:\n", i);
        p.CountryRoads(Town);
        p.DelGraph();
    }
}
 
/*
и наконец то функция для поиска дорог.
*/
void Graph::CountryRoads(int Town){   //вообще требуется только Town. вторая для красоты работы функции For
    for(int i=0;i<nu;i++){      //пройдем все города. найдем дороги до каждого города от нашего города, номер которой пришел в переменной Town
        if(i==Town){        //случай, когда один и тот же город
            printf("0\n");
            continue;
        }
 
        bool *visited=new bool[nu];     //первый булевый массив
        for(int j=0;j<nu;j++){
            visited[j]=false;       //ставим везде ложь
        }
        visited[Town]=true;     //ставим правду на пройденном первом городе
 
        queue <reg> q;      //нужна будет очередь
        q.push(reg(Town,0,visited,nu));         //номер города_maxCost до этого города включительно_пройденные уже города по этой ветке, включая этот
 
        delete visited;     //удаляем массив, он больше не нужен.
 
        int minCost=0;      //главный счетчик costRoad
 
        while(!q.empty()){        //пока есть города в очереди, пока не пройдены все варианты движения
            reg Town_cost_vis=q.front();        //вытаскиваем данные о городе для просмотра всех его веток к другим городам
            q.pop();
 
            for(E *p=mass[Town_cost_vis.first.first];p!=NULL;p=p->next){          //смотрим все города, с которым связан наш нынешний город из очереди
                int maxCost=max(p->info.second,Town_cost_vis.first.second);     //здесь сохраняем цену города. нам нужен больший. сравниваем цены предшествующих городов этой ветки и цену до нынешнего города
                if(p->info.first==i&&minCost==0){       //если мы нашли наш конечный город в первый раз, то сразу запишем цену до него. будет, с чем вести сравнение
                    minCost=maxCost;
                    continue;
                }
                if(p->info.first==i&&minCost>maxCost){      //если мы нашли наш конечный город не в первый раз, то запишем меньшую цену до него.
                        minCost=maxCost;
                        continue;
                }
                if(p->info.first!=i&&Town_cost_vis.second[p->info.first]==false&&(!(minCost>0)||p->info.second<minCost)){       //если это не конечный город и здесь мы еще не были, гуляя по именно этому пути, то закинем его в очередь
                    bool *copy=new bool[nu];        //для этого создадим новую булевую функцию и сделаем копию той, что хранилась в данных из очереди
                    for(int j=0;j<nu;j++){
                        copy[j]=Town_cost_vis.second[j];
                    }
                    copy[p->info.first]=true;       //к уже пройденным городам добавим наш добавляемый в очередь город
                    q.push(reg(p->info.first,maxCost,copy,nu));     //вот и добавили
                    delete copy;        //удалим массив
                }
            }
        }
        if(minCost==0){     //случай, когда мы ни разу не попали в конечный город
           printf( "Impossible\n");
        }else{      //случай, когда попали
           printf( "%d\n", minCost);
        }
    }
}
 
void Graph::DelGraph(){
    for(int i=0;i<nu;i++){
        while(mass[i]!=NULL){
            E *q=mass[i];
            mass[i]=mass[i]->next;
            delete q;
        }
    }
    delete[] mass;
    nu=0;
}
 
/*
функция main.
*/
int main(){
    int n;
    scanf( "%d", &n);
    For(n);
    getch();
    return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 06:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru