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

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

Войти
Регистрация
Восстановить пароль
 
vizapromo
18 / 11 / 1
Регистрация: 04.12.2012
Сообщений: 51
#1

Функция bfs - C++

26.12.2012, 17:03. Просмотров 975. Ответов 3
Метки нет (Все метки)

Приветствую всех!!, У меня никак не получается одна задачка связанная с функцией bfs((. Напишите код пожалуйста... Вот и сама задачка:

В столице одной небольшой страны очень сложная ситуация. Многокилометровые пробки буквально парализовали движение в городе, и власти на многих улицах ввели одностороннее движение, не анализируя, можно ли будет теперь проехать из любого места в городе в любое другое, не нарушая правила. Транспортная система столицы представляет собой N площадей, соединенных M полосами для движения, в том числе круговыми полосами, проходящими по площади. Каждая полоса предназначена для движения только в одну определенную сторону. По круговой полосе можно двигаться только внутри площади и только против часовой стрелки.
Власти города на каждой полосе разместили видеокамеру, поэтому если Андрей едет по встречной полосе (при её наличии) или, в случае одностороннего движения, в сторону противоположную предписанной знаками, то после поездки против правил по каждой из полос ему придется заплатить штраф в размере одной тысячи тугриков этой страны.
Андрей, который торопится купить товар со скидкой, решил доехать до магазина в любом случае, даже если для этого придется нарушать правила. Но он хочет выбрать такой маршрут движения, суммарный штраф на котором минимален.
Андрей ещё не решил, откуда именно и в какой магазин он собирается ехать, поэтому ему необходимо ответить на несколько вопросов вида "Какой минимальный штраф надо заплатить, чтобы добраться из пункта А в пункт В?". Отвечая на потребности жителей столицы, известная поисковая система Индекс разрабатывает соответствующий сервис.
Помогите этой поисковой системе.
Формат входных данных:
В первой строке входных данных содержатся два числа N и M - количество площадей и полос движения в городе соответственно (1 <= N <= 5000, 1 <= M <= 10000). Далее содержатся описания полос, по которым движение разрешено. Каждая полоса описывается номерами двух площадей, которые она соединяет. Движение разрешено в направлении от первой из указанных площадей ко второй.
В следующей строке содердится одно число К - количество вопросов у Андрея (1 <= k <= 10000, N*K <= 2 * 10^7). В следующих строках описываются вопросы, каждый вопрос описывается номерами двух площадей, между которыми требуется найти дешевый путь. Путь необходимо продолжить от первой из указанных площадей ко второй.
Формат выходных данных:
Для каждого вопроса выведите одно число - искомый минимальный размер штрафа в тысячах тугриков. В случае, если пути между выбранной парой площадей не существует, выведите "-1".

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

Выходные данные:
0
2
0

Добавлено через 30 минут
up up

Добавлено через 34 минуты
Никто не ответит??(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.12.2012, 17:03     Функция bfs
Посмотрите здесь:

Обход графа в ширину - Breadth First Search (BFS) - C++
Всем привет! Я не понимаю алгоритм обхода в глубину BFS:( Кто может помощь?

1C 8.x BFS на 1С - 1С
Кто-нибудь писал на 1С обход графа в ширину? Поделитесь кодом...

Нужен пример алгоритма BFS - Pascal
Здравствуйте. Помогите мне запрограммировать на Паскаль алгоритм BFS или дайте ссылку на программу. Сам алгоритм я знаю осталось лишь...

Отсутствие пути при решении BFS - Java SE
Подскажите, пожалуйста, в чём может быть проблема. Считываю с файла лабиринт, перевожу его в графы, решаю в графах и выдаю ответ в...

Функция sqrt: существует более одного экземпляра. Функция перегруженная - C++
#include &lt;iostream&gt; #include &lt;math.h&gt; #include &lt;iomanip&gt; using namespace std; int main(){ float s, p; int c, a; s=0; ...

Функция удаления текста в скобках [2], непосредственно функция + 12кб вложений - C++
Доброго времени суток, случилось так, что пришлось работать с с-строками (лаба, угу), в которой нужно удалить весь текст в скобках,...

Перегрузка операций: friend-функция или функция-член класса - C++
Здравствуйте, меня интересует вопрос, в чем разница при перегрузке операторов через operator и friend. Вот к примеру такой код. class...

какую библиотеку надо подключать чтоб работала функция _getch() и функция cin.get() - C++
какую библиотеку надо подключать чтоб работала функция _getch() и функция cin.get()

Выясните, сохраняет ли булева функция 0, 1, является ли функция линейной, монотонной, само двойственной? - Дискретная математика
Помогите пожалуйста!!! Булева функция задана вектором значений F(x)=(1001) Выясните, сохраняет ли эта функция 0, 1, является ли эта...

Функция - Pos(s,s1). Назначение - поиск первого вхождения подстроки s1 в строку s (аналогичная функция C - strstr) - C (СИ)
Функция - Pos(s,s1). Назначение - поиск первого вхождения подстроки s1 в строку s (аналогичная функция C - strstr).Помогите плииз

Функция нахождения максимума в строке матрицы и функция вычисления ||D|| - Pascal
Помогите написать программу. Заранее спасибо. Даны вещественные матрицы A, B, C размером 5x6. Вычислить величину ...

Функция DisplayTranslucentSprite функция стала игнорировать параметр прозрачности - Pure Basic
Здравствуйте. Что-то изменил в коде так, что функция стала игнорировать параметр прозрачности, т.е. при любом значении спрайт отображается...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
vizapromo
18 / 11 / 1
Регистрация: 04.12.2012
Сообщений: 51
28.12.2012, 08:52  [ТС]     Функция bfs #2
up up
Nixy
ComfyMobile
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
28.12.2012, 09:02     Функция bfs #3
много букв, вам проше выложить свои наработки и спросить по ним
MilosedOFF
3 / 3 / 0
Регистрация: 13.06.2012
Сообщений: 50
28.12.2012, 14:20     Функция bfs #4
Я сдал ее. Погугли:"Алгоритм Дейкстры в нагруженном графе".
Yandex
Объявления
28.12.2012, 14:20     Функция bfs
Ответ Создать тему
Опции темы

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