Task 104. Кошки - мышки
UniLecsЗадача: мышка пытается пробежать по городу, спасаясь от голодных котов. Ей нужно преодолеть путь от 1го перекрестка до последнего, но на каждой улице ее поджидают сумасшедшие коты. Мышке нужно пройти так, чтобы вероятность спастись была максимальна. Помогите найти ей такой маршрут.
Входные данные: N - кол-во перекрестков, RoadArr - массив, ктр определяет каждую улицу. Элемент массива RoadArr содержит 3 значения: a, b - перекрестки, между ктр проходит улица, SafeValue - вероятность спастись от котов на этой улице. Есть только одна улица между любыми 2мя перекрестками.
Вывод: вывести самый безопасный маршрут для мышки и общую вероятность спастись на этом маршруте.
Пример: N = 4,
RoadArr = (1, 2, 98), (1, 3, 50), (1, 4, 20), (2, 4, 99), (3, 4, 70)
Answer: Безопасный маршрут: 1 - 2 - 4; вероятность спасения на маршруте = ~97.02
Идея: задачу можно решить с помощью классического алгоритма Дейкстры. Алгоритм Дейкстры находит кратчайшие пути от одной из вершин графа до всех остальных. В нашем случае вместо суммирования длин дорог, мы используем произведение вероятностей спасения на улице.
Более подробные комментарии к решению смотри в коде!
Даный алгоритм очень популярен и применяется в решении многих задач, поэтому в будущем мы к нему еще вернемся. А пока более подробную информацию вы можете найти тут:
Реализация:
https://gist.github.com/unilecs/5bd1e92491da6515cf80350f4d821136
Test: