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

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

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

Задача по графам - C++

03.02.2013, 13:47. Просмотров 354. Ответов 0
Метки нет (Все метки)

Всем привет!

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

Степан недавно купил автомобиль, но водительские права еще не получил. В связи с этим он не имеет права на нем ездить. Но его жена уже спланировала выходные, и поездка в столицу входит в эти планы. Недолго думая, Степан нашел выход. Известно, что ГАИ стоят не на всех дорогах, а лишь на тех, которые обойти нельзя, потому что так они поймают больше правонарушителей. Известно, что в стране Степана N городов, и они соединены M дорогами. Разумеется, никакие две дороги не соединяют одну и ту же пару городов (в стране же умные люди работают). Степан живет в городе А, а столица находится в городе 1. За отсутствие водительских прав штраф составляет 1000 рублей. Скажите, сколько у него должно быть при себе денег, чтобы он мог выплатить все штрафы.

Входные данные: Первая строка содержит два числа N, M (2 ≤ N ≤ 105, 1 ≤ M ≤ 105). Другие М строк содержат два числа Xi и Yi, описывающих дорогу между городом Xi и городом Yi. В последней строке написано число A (2 ≤ A ≤ N) - город в котором живет Степан.

Выходные данные: Выведите в одной строке единственное число - количество рублей которые Степан должен иметь при себе.

Пример:
Входные данные:
6 7
1 2
2 3
3 1
3 4
4 5
4 6
5 6
6

Результат:
1000
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.02.2013, 13:47
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача по графам (C++):

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

Книги по графам - C++
Подскажите пожалуйста, по какой книге лучше всего начать изучение графов в с++ с нуля? и если возможно, киньте ссылку

Литература по графам, деревьям С++ - C++
Доброго времени суток. Подскажите пожалуйста, где можно почитать про деревья. Желательно с примерами реализации.

Ищу информацию по графам (кратчайший цикл) - C++
Здравствуйте, я ищу информацию по циклам. У меня задачка найти кратчайший цикл в графе. Вот и я бы хотела литературу где описана данная...

Задача по Графам - Дискретная математика
Столкнулся с задачей на графы... Вот условие: Составьте все возможные планы маршрута путешествия по историческим местам, если...

алгоритм по графам - Алгоритмы
Всем привет! Занимаюсь изучением динамического программирования при решении задач для графов. У меня 3 задачи: 1. Алгоритм...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.02.2013, 13:47
Привет! Вот еще темы с ответами:

книги по графам - Turbo Pascal
Подскажите, какие учебники лучше всего подходят для изучения графов в турбо паскале?? в интернете я ничего хорошего не нашла, а учебники,...

Задание по графам - Ruby
Проверить достижимость в графе одной вершины из другой. Граф задан списком ребер. Примеры: в графе ((1 2)(2 3)(3 4)(1 5)) вершина 4...

FAQ по графам - Pascal
Иногда на форуме появляются просьбы решить задачу на теорию графов. На теории такие задачи решаются не так уж и сложно, ведь сколько...

Задачи по комбинаторике и графам - VBA
1. Найти количество перестановок из N объектов, количество размещений и сочетаний из N по M объектов. Найти k-ый комбинаторный объект в...


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

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

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