АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

9. Сеть

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Имеется телекоммуникационная сеть, состоящая из N приемно-передающих станций (N<100). По объективным причинам надежность передачи сообщений между различными станциями различается. На рисунке показан фрагмент такой сети, содержащий 7 станций.

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

Исходные данные

В первой строке содержится 4 целых числа: количество станций N, количество дуг M, номер станции-источника и станции-приемника (различные целые положительные числа, не превышающие N). Далее следуют M строк, каждая из которых содержит информацию об одной дуге сети: номер источника, номер приемника и вероятность успешной передачи сообщения от данного источника к данному приемнику (положительное число, не большее единицы).

Результат

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

Пример

Исходные данныеРезультат
7 12 1 7
1 2 0.8
1 3 0.3
1 4 0.65
2 4 0.9
3 4 0.85
2 5 0.5
3 6 0.95
4 5 0.7
4 6 0.6
5 6 0.5
5 7 0.8
6 7 0.9
1 2 4 5 7
0.4032

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / VI Межвузовская олимпиада 2003 /
93. E - Предметный указатель 9. 8. G - Скобки 96. H - Последовательность
Задачи по темам / Графы /
246. Путь в лабиринте 9. 297. Скачки 64. Считай путем 891. Упаковка дерева
Учебные курсы / Алгоритмы и структуры данных / Алгоритмы на графах /
246. Путь в лабиринте 9. 297. Скачки 247. Удаление клеток 1968. Эвакуация
Задачи с соревнований / Тренировки ВоГУ / Графы: обходы и кратчайшие пути /
204. B - Переливания 9. 205. D - Игра в города 890. E - Лабиринт.
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, смена 2019 / Графы /
1970. 12 - Автобусы 9.
 
время генерации 0.125 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.