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

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

Восстановить пароль Регистрация
 
GogenMarat
Сообщений: n/a
05.04.2013, 22:47     Решение задачи на графы. Country Roads #1
Добрый вечер. Писал я тут решение на следующую задачу с сайта 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.04.2013, 22:47     Решение задачи на графы. Country Roads
Посмотрите здесь:

C++ Задачи на графы и строки
Задачи на графы C++
Решение задачи c++ C++
C++ Решение задачи
C++ Решение задачи
C++ Решение задачи
Решение задачи C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 19:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru