Форум программистов, компьютерный форум CyberForum.ru
CyberForum.ru - форум программистов и сисадминов > > >
Восстановить пароль Регистрация

Ответ Создать новую тему
 
Serpanok
Новичок
0 / 0 / 0
Регистрация: 30.11.2011
Сообщений: 4
03.02.2013, 13:47     Задача по графам
  #1
Всем привет!

помогите решить задачу, я так понял что тут графы, а я в них полный 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
AdAgent
Объявления
03.02.2013, 13:47
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать новую тему

Похожие темы
Тема Раздел Ответов Автор Дата
C++ Ищу информацию по графам (кратчайший цикл)
Здравствуйте, я ищу информацию по циклам. У меня задачка найти кратчайший цикл в графе. Вот и я бы хотела литературу где описана данная задача. Хотяб алгоритм. Не могли вы бы скинуть литературу(если...
С++ для начинающих 1 Merasada 02.05.2014 21:31
C++ Алгоритм по графам
Добрый день. Нашел готовый алгоритм по нахождению, существует ли путь с одной вершины в другую вершину графа. http://www.cyberforum.ru/cpp-beginners/thread850719.html#post4484372 Внедрил функцию в...
С++ для начинающих 0 zewer 17.01.2014 01:42
C++ Литература по графам, деревьям С++
Доброго времени суток. Подскажите пожалуйста, где можно почитать про деревья. Желательно с примерами реализации.
С++ для начинающих 1 chizz 27.05.2013 16:02
C++ Книги по графам
Подскажите пожалуйста, по какой книге лучше всего начать изучение графов в с++ с нуля? и если возможно, киньте ссылку
С++ для начинающих 6 Паха 28.04.2013 22:22
C++ С++.Написание программы по графам
Помогите, плиз....с написание программы на С++.....Суть программы: в каком порядке нужно удалять вершины графа, чтобы не нарушать связность графа.
С++ для начинающих 0 morozixa939 20.12.2012 20:18
C++ Задачка по графам
Здравствуйте уважаемые знатоки! Необходима помощь по графам. Написал прогу, но не могу откомпилировать. Сломал голову, пытаясь понять суть ошибок. Может кто поможет в разборе кода? Файл graph.h ...
С++ для начинающих 5 kdv12 29.03.2012 23:33
C++ задача на массивы и задача на матрицы
Только начал учиться программировать, великие проблемы с зачетом. Прошу помочь дописать или исправить первую задачу и решить 2-ую и 3-ю. Объясните пожалуйста как решаются. Защищать после надо задачи...
С++ для начинающих 0 D93 26.12.2011 00:12
Опции темы

Текущее время: 19:25. Часовой пояс GMT +4.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.7 PL3
Copyright ©2000 - 2014, vBulletin Solutions, Inc.