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

Найти маршрут, при котором радость Петра будет наибольшей

03.05.2017, 16:30. Просмотров 452. Ответов 0
Метки нет (Все метки)

Вопрос жизни и смерти.Не знаю как сделать программу,очень нужно!

На отдыхе в Теплой Стране Вера познакомилась с симпатичным волейболистом- трактористом Петром. Турист Петр, кстати, собирается после отличного отдыха в Теплой Стране отправиться в путешествие по городам Европы. Как известно, Европа обладает развитой транспортной системой: в Европе есть V интересующих Петра городов и E маршрутов ночных поездов. Каждый маршрут соединяет два различных города, время в пути составляет одну ночь. Поезда по маршруту ходят в обоих направлениях.

Основной целью поездки Петра является осмотр местных достопримечательностей. По- скольку Петр — невероятно занятой человек, то он решил, что все путешествие должно занимать не более четырех дней. Петр уже многое повидал, поэтому на осмотр достопримечательностей в каждом городе Петр тратит ровно один день. Он хочет составить наиболее практичный тур: каждый день он будет тратить на осмотр города, а каждую ночь — на переезд ночным поездом между городами. Разумеется, Петр не имеет ни малейшего желания посещать один город несколько раз.

Но на этом прагматичность Петра не заканчивается: Петр, как настоящий турист, хочет посмотреть на самые красивые европейские достопримечательности. Он долго изучал справочники и для каждого города оценил свою ожидаемую радость от его посещения pi. Теперь он хочет найти маршрут, при котором его радость будет наибольшей. Помогите Петру найти такой маршрут.

Формат входного файла
В первой строке входных данных заданы два целых числа V и E (1 ≤ V; E3<=10*5) — количество городов и маршрутов поездов, соответственно. В следующей строке заданы V целых чисел pi (1 ≤ pi ≤ 108), где pi обозначает ожидаемую радость от посещения го- рода с номером i. В следующих E строках заданы описания маршрутов поездов. Каждое описание состоит из пары различных чисел ai и bi (1 ≤ ai; bi ≤ V) — номеров городов, между которыми курсирует этот маршрут поезда. Гарантируется, что между каждой парой городов существует не более одного маршрута поезда.

Формат выходного файла
В первой строке выходных данных выведите число K (1 ≤ K ≤ 4) — количество городов в оптимальном маршруте туриста Петра. В следующей строке выведите номера этих городов в порядке посещения. Города нумеруются начиная с единицы. Если оптимальных маршрутов несколько, выведите любой из них.
Примеры
входные данные
5 4
4 2 3 1 5
1 2
2 3
3 4
4 5
выходные данные
4
2 3 4 5
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.05.2017, 16:30
Ответы с готовыми решениями:

Найти такое i при котором введенное с клавиатуры M будет меньше F
#include &lt;QCoreApplication&gt; #include &lt;stdio.h&gt; #include &lt;math.h&gt; #include &lt;iostream&gt; int...

Найти угол при вершине данной плоскости, при котором груз будет иметь минимальное ускорение
Небольшое тело движется по наклонной плоскости под действием силы, модуль которой вдвое больше силы...

Необходимо найти Х, при котором выражение будет истинным
найти Х , при котором выражение будет истинным A*B+X(B :с чертой&quot; +А*С &quot;с чертой у...

Найти значение Р2 при котором теоретическая скорость истечения будет критической.
Воздух при Р=0,5 мПа и t1= 27 градусов Цельсия адиабатно вытекает из ресивера. Найти значение Р2...

Найти такие значения цифр, при которых сумма цифр в итоге будет наибольшей
Условие: расшифровать ребус где одинаковые цифры заменили одинаковыми буквами. Найти такие значения...

0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.05.2017, 16:30

Найти значения медианы, при котором модуль разности сумм будет минимальна
Добрый день! Может быть, кто-то сталкивался? Из раздела обработки сигнала. Дана матрица E. Нужно...

Найти наибольшее значение угла, при котором шар не будет делать скачка
Шар радиуса r катится без проскальзывания по горизонтальной плоскости, переходя с этой плоскости на...

Найти максимальный угол наклона плоскости, при котором цилиндр не будет скатываться
Цилиндр радиусом \mathit{R} имеет цилиндрическое отверстие радиусом \mathit{r=\frac{R}{2}} , ось...


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

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

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