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

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

Войти
Регистрация
Восстановить пароль
 
Bison5
0 / 0 / 0
Регистрация: 27.11.2016
Сообщений: 3
#1

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

30.11.2016, 11:02. Просмотров 227. Ответов 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
Я подобрал для вас темы с готовыми решениями и ответами на вопрос сложная задача с олимпиады по программированию (C++):

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

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

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

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

Вроде простая задача и в то же время сложная - C++
Вот условие: написать программу позволяющую выводить числа начиная от 0.000000001 до 10000000000 с некоторым шагом. Как это можно...

Как решается эта сложная задача - C++
Как решить? Если у массива А(40) есть элемент, равный В, то отсортировать элементы, находящиеся после него по убыванию сортировкой...

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

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

Сложная задача!Волосатый бизнес!Про неформала! - C++
написать с++ Волосатый бизнес Одного неформала выгнали с работы, и теперь ему надо как-то зарабатывать себе на пиво и сигареты....

Не сложная элементарная легкая задача с хэдерами,поинтерами и тд - C++
Здравствуйте, ребята! Столкнулась с задачей..времени,как всегда не хватает(( Вообщем, есть задача у меня такая: #include<iostream> ...

Сложная задача или есть ли в C++ типы с порядком в 30 цифр? - C++
Собственно говоря вот задача, хз как её решать, если запретили использоваться библиотеки для обработки больших чисел, а стандартные...


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

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

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