Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Bison5
0 / 0 / 0
Регистрация: 27.11.2016
Сообщений: 3
#1

сложная задача с олимпиады по программированию

30.11.2016, 11:02. Просмотров 240. Ответов 2
Метки нет (Все метки)

Перевозчику необходимо доставить груз из одного города (А) в другое (В). Известно, что при доставке груза перевозчик несет затраты связанные по транспортировке товара и оплате «пошлины» [взимается определенная сумма при проезде через город транзитом], в городах ((А)(В)) с которого и до которого перевозится товар «пошлину» с перевозчика не оплачивается.

Составить программу которая находит оптимальный маршрут доставки товара между двумя городами. Суммы «пошлины», которые взимает каждое из городов известны. Известна также информация о том, между какими городами есть прямое соединение и стоимость перевозки по этому соединенные.

Входные данные

Первая строка входного файла содержит два целых числа N (количество городов) (1≤N≤100) и M (количество дорог) (1≤M≤100) .

Вторая строка содержит N действительных чисел, которые задают сумму «пошлины» для каждого из городов. В каждом следующем из M строк файла содержится тройка чисел (для примера тройка 2 5 130 - задает сообщение между вторым городом и пятым и затраты на транспортировку). В последней строке файла заданы два целых числа ( А и В) .

Исходные данные

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

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.11.2016, 11:02
Ответы с готовыми решениями:

Он-лайн олимпиады по программированию
Подскажите, если кто знает, пожалуйста, он-лайн олимпиады по программированию....

Задача из олимпиады
Здравствуйте уважаемые форумники. На днях столкнулся с задачкой из одной...

очень сложная задача
не получается ничего

Не сложная задача на матрицу и еще
1)Составить элементы столбцов заданной матрицы размером 4 × 3. Результат...

Сложная задача про треугольники С++
Миша любил рисовать треугольники, но делал он это необычным способом. Сначала...

2
J5
25 / 25 / 9
Регистрация: 22.12.2013
Сообщений: 85
30.11.2016, 11:46 #2
Bison5, точно помню, что расчет оптимального пути есть в книге Роберта Лафоре по алгоритмам, в последних главах связанных с графами, а так же у Сэджвика (все по тем же алгоритмам).
0
MrGluck
Модератор
Эксперт CЭксперт С++
8054 / 4898 / 1426
Регистрация: 29.11.2010
Сообщений: 13,296
30.11.2016, 11:48 #3
Решается "сложная" задачка элементарно с помощью алгоритма Дейкстры.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.11.2016, 11:48

Вроде простая задача и в то же время сложная
Вот условие: написать программу позволяющую выводить числа начиная от...

Сложная задача про полный квадрат
Есть 9 разных чисел a,b,c,d,e,f,g,h,i. Сумма любых двух разных чисел из данного...

Как решается эта сложная задача
Как решить? Если у массива А(40) есть элемент, равный В, то отсортировать...


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

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

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