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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
PG94
2 / 2 / 0
Регистрация: 15.01.2012
Сообщений: 181
#1

Задача на алгоритм Дейкстры (как лучше хранить информацию?) - C++

20.09.2012, 20:37. Просмотров 664. Ответов 1
Метки нет (Все метки)

Доброго времени суток.
Есть задача:
Одна из команд-участниц олимпиады решила вернуться домой на электричках. При этом ребята хотят попасть домой как можно раньше. К сожалению, не все электрички идут от города, где проводится олимпиада, до станции, на которой живут ребята. И, что еще более обидно, не все электрички, которые идут мимо их станции, останавливаются на ней (равно как вообще, электрички останавливаются далеко не на всех станциях, мимо которых они идут). Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E. Напишите программу, которая по данному расписанию движения электричек вычисляет минимальное время, когда ребята могут оказаться дома.
Входные данные
Во входном файле записаны сначала числа N (2 ≤ N ≤ 100) и E (2 ≤ E ≤ N). Затем записано число M (0 ≤ M ≤ 100), обозначающее число рейсов электричек. Далее идет описание M рейсов электричек. Описание каждого рейса электрички начинается с числа Ki (2 ≤ Ki ≤ N) — количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе — время, когда электричка останавливается на этой станции (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.
Выходные данные
В выходной файл выведите одно число — минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите –1.
Есть идея хранить входные данные след. образом:
Выделить в памяти 2-х матрицы(Tab1 и Tab2 например) одинаковой размерности, где строки - рейсы, столбцы - номера станций. В каждой ячейке Tab1 будет время прибытия i-oй электрички(i - номер строки), на j - ую станцию, причём в Tab2[i][j] будет номер станции, на которой электричка электричка остан. в следующий раз.
Подскажите, как можно лучше организовать хранение данных. Спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.09.2012, 20:37
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача на алгоритм Дейкстры (как лучше хранить информацию?) (C++):

Как лучше всего хранить коэффициенты? - C++
Мне нужно работать с матрицей порядка 100 000. Она сильно разреженная, по этому хранить все коэффициенты - не вижу смысла. Стало быть нужно...

Оконный менеджер. Как лучше хранить указатели на элементы менеджера? - C++
Привет! Делаю тут 3D движок :wizard: В общем есть главный класс движка mgeSystem, так же есть класс окна mgeWindow, который не...

Алгоритм Дейкстры - C++
Помогите найти ошибку плз. Первый шаг алгоритма выполняет правильно,а дальше-нет. #include<iostream> #include<fstream> ...

Алгоритм Дейкстры С++ - C++
Реализовать алгоритм поиска кратчайшего пути. Алгоритм Дейкстры. Представление графа – матрица смежности. как можно после того как...

Алгоритм Дейкстры - C++
Что-то у меня Дейкстра не работает... прошу помощи у вас... Сам уже часа 1.5 сижу и не могу найти ошибку...#include <iostream> #include...

Алгоритм Дейкстры - C++
Написал программу, проверил код, в MVS6 С++ компилируется без ошибок. Но вот не задача, программа рушиться(не выполняется) при количестве...

1
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
20.09.2012, 20:52 #2
Я лично решал это через алгоритм Форда-Беллмана и, соответственно, просто хранил список ребер.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.09.2012, 20:52
Привет! Вот еще темы с ответами:

Алгоритм Дейкстры - C++
Как на С++ в консольном приложении описать алгоритм Дейкстры?

Алгоритм Дейкстры - C++
Добрый день, помогите пож-та решить задачи на с++. Нашел решение (расписаны все алгоритмы, процедуры подсчета и т. д.), но сложность...

Алгоритм Дейкстры - C++
Всем добрый день,уважаемые программисты! Помогите пожалуйста решить вот эту задачу алгоритмом дейкстры. Вроде сам алгоритм правильно...

Алгоритм Дейкстры - C++
Пытаюсь сейчас его понять, как я понял сперва надо оставить матрицу смежности, и все возможные связи между вершинами заполнить их длинами,...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru