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

Не могу понять ошибку. При вводе значений вылетает программа. - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Найти путь из А в И http://www.cyberforum.ru/cpp-beginners/thread392027.html
Есть у нас точка А и точка В. Идем с А в В, найти пути, которые будут равны 250 и 350 очок. Одна из идей - построить биннарное дерево и обойти. Собственно, интересует как лучше (читать правильно)...
C++ функция класса - вызов есть класс Graph с функцией int OutputMatrix(int i,int j); и матрица int **Matrix; в области private, в cpp я описал функцию: int Graph::OutputMatrix(int i,int j){ int k; k=Matrix; ... http://www.cyberforum.ru/cpp-beginners/thread392022.html
Поиск в стеке! C++
Помогите решить: нужно найти сколько элементов стека находится между его минималь- ным и максимальным элементами. Вот что у меня есть #include <iostream> using namespace std; struct tstk...
Прямоугольный массив, сортировка C++
В прямоугольном массиве(7 на 8) с по-мощью процедуры сделать все строки упорядоченными по воз-растанию. Исходные числа из файла читать, начиная с "К"-го числа, где К<10 вводить с кла-виатуры. 1)...
C++ Задачка(одномерные массивы и матрицы) http://www.cyberforum.ru/cpp-beginners/thread392000.html
Уважаемые форумчане, помогите пожалуйста написать программку... Суть программы: "Дан целочисленный массив из N элементов. Если элементы массива представляют собой знакочередующуюся...
C++ Добавление элементов в односвязный список У меня проблема.Мне надо сделать добавление в односвязный список К элементов, начиная с заданного номера.Не могу никак это реализовать.:cry: //Создание и печать однонаправленного списка #include... подробнее

Показать сообщение отдельно
Xalik
Сообщений: n/a

Не могу понять ошибку. При вводе значений вылетает программа. - C++

26.11.2011, 01:55. Просмотров 482. Ответов 0
Метки (Все метки)

Задача: Дана система 2-х сторонних дорог. Известна цена на каждом пути. Определить убыток при закрытии дороги.

Алгоритм: Функция "poisk" в моей программе находит в графе и выводит самый дешёвый путь (вершины) и его цену. Функция "del" удаляет в матрице инцидентности цену на указанном пути. Исходные данные с файла, где 1 строка кол-во вершин.

Проблема: Прога работает лишь при использовании функции poisk. а всё остальное игнорирует и зависает. Нужна помощь!

Код:
//Поиск самого дешевого пути
#include <iostream>
#include <conio.h>


#define VERTEXES 20 //Число вершин в графе
using namespace std;
int d1,d2;
//---------------------------------------------------------------------------
int poisk(int a[VERTEXES][VERTEXES],int n,int s,int g)
{ int u,v;
int ukst=-1;
int stack[VERTEXES];
int infinity=1000; // Бесконечность
int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины,
// x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
// x[i]=1 - самый дешеывй путь в i-ю вершину уже найден
int t[VERTEXES]; //t[i] - длина самого дешевого пути от вершины s в i
int h[VERTEXES]; //h[i] - вершина, предшествующая i-й вершине
// на самом дешевом пути
for (u=0;u<n;u++)
{
t[u]=infinity; //Сначала все кратчайшие пути из s в i
//равны бесконечности
x[u]=0; // и нет кратчайшего пути ни для одной вершины
}
h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
t[s]=0; // Кратчайший путь из s в s равен 0
x[s]=1; // Для вершины s найден кратчайший путь
v=s; // Делаем s текущей вершиной


/* for (u=0;u<k;u++)
{
cin>>d>>b>>c;
a[d][b]=a[b][d]=c;
};*/

while(1)
{
// Перебираем все вершины, смежные v, и ищем для них самый дешевый путь
for(u=0;u<n;u++)
{


if(a[v][u]==0)continue; // Вершины u и v несмежные
if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не найден самый дешевый путь
// и новый путь в u дешевле чем старый, то

{
t[u]=t[v]+a[v][u]; //запоминаем более дешевую длину пути в
//массив t и
h[u]=v; //запоминаем, что v->u часть самого дешевого
//пути из s->u
}
}

// Ищем из всех длин недешевых путей самый дешевый
int w=infinity; // Для поиска самого дешевого пути
v=-1; // В конце поиска v - вершина, в которую будет
// найден новый самый дешевый путь. Она станет
// текущей вершиной
for(u=0;u<n;u++) // Перебираем все вершины.
{
if(x[u]==0 && t[u]<w) // Если для вершины не найден самый дешевый
// путь и если цена пути в вершину u меньше
// уже найденной, то
{
v=u; // текущей вершиной становится u-я вершина
w=t[u];
}
}
if(v==-1)
{
cout<<"HeT nyTu u3 BepwuHbI "<<s<<" B BepwuHy "<<g<<"."<<endl;
break;
}
if(v==g) // Найден самый дешевый путь,
{ // выводим его
cout<<"CaMbIu deweBbIu nyTb u3 BepwuHbI "<<s<<" B BepwuHy "<<g<<" : ";
u=g;
cout<<s<<" ";
while(u!=s)
{
// cout<<" "<<u;
stack[++ukst]=u;
u=h[u];
}
while (ukst>-1) cout<<stack[ukst--]<<" ";// вывод пути

cout<<" . LI,eHa nyTu - "<<t[g];
break;
}
x[v]=1;
} return 0;
}

//---------------------------------------------------------------------------
int del(int a[VERTEXES][VERTEXES])
{

cout<<"\n goroda dl9 ydaleni9: ";
cin>>d1;
cout<<"\n goroda dl9 ydaleni9: ";
cin>>d2;
a[d1][d2]=0;
a[d2][d1]=0;
return 0;
}





int main()
{
// clrscr();

int n= VERTEXES; // Количество вершин в графе
int a[VERTEXES][VERTEXES]={0};


// Будем искать путь из вершины s в вершину g
int s; // Номер исходной вершины
int g,k,d,b,c,d1,d2; // Номер конечной вершины



cout<<"BBeguTe roPod otkyga Ha4uHaeTc9 nyTb: "; // Номер может изменяться от 0 до p-1
cin>>s;
cout<<"BBeguTe ropod rde 3akoH4uTc9 nyTb: ";
cin>>g;



freopen("input.txt","r",stdin);
int i,j; // для чтения из файла
cin>>n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>a[i][j];


// Инициализируем начальные значения массивов
// Счетчик вершин
poisk(a,n,s,g);
del(a);
poisk(a,n,s,g);

getch();



}
/*Программа запрашивает вершины s и q и выводит кратчайший путь. Например, после ввода s = 3, q = 6, программа выводит

Нет пути из вершины 3 в вершину 6.

После ввода s = 0, q = 2 программа выводит

Самый дешевый путь из вершины 0 в вершину 2: 2 5 1 0. Цена пути = 3.*/

Добавлено через 13 минут
я конечно не дописал прогу до конца (нахождение убытка), но это пока не суть, т.к. уже виснет
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru