Джеймс Дэвис – 40 задач на Python (страница 7)
Каждый проход имеет определенную стоимость прохождения, которая может быть как положительной, так и отрицательной. Исследователи хотят найти путь с минимальной суммарной стоимостью прохождения из комнаты 1 в комнату N.
Напишите программу, которая поможет исследователям найти минимальную стоимость прохождения лабиринта.
Входные данные:
– Первая строка содержит два целых числа: N (2 <= N <= 10^5) – количество комнат, и M (1 <= M <= 2*10^5) – количество проходов между комнатами.
– Следующие M строк содержат описание проходов. Каждая строка содержит три целых числа: a, b и w (1 <= a, b <= N, -10^3 <= w <= 10^3), где a и b – номера комнат, соединенных проходом, а w – стоимость прохождения этого прохода.
Выходные данные:
– Одно целое число – минимальная суммарная стоимость прохождения из комнаты 1 в комнату N. Если путь не существует, вывести -1.
Примеры:
Пример 1:
Входные данные:
5 7
1 2 4
1 3 2
2 3 5
2 4 10
3 4 -3
3 5 3
4 5 4
Выходные данные: 6
Пример 2:
Входные данные:
3 2
1 2 1
2 3 1
Выходные данные: 2
Решение:
Для нахождения минимальной суммарной стоимости прохождения лабиринта из комнаты 1 в комнату N мы можем воспользоваться алгоритмом поиска кратчайшего пути в графе. Мы будем использовать алгоритм Дейкстры для нахождения кратчайшего пути от вершины 1 до вершины N.
Псевдокод:
ввод N, M
инициализация графа G
для каждого i от 1 до M:
ввод a, b, w
добавить ребро (a, b) со стоимостью w в граф G
вызвать алгоритм Дейкстры для поиска кратчайшего пути от вершины 1 до вершины N в графе G
вывод результат
Реализация на Python:
```python
import heapq
def dijkstra(graph, start, end):
pq = [(0, start)]
distances = {v: float('inf') for v in graph}
distances[start] = 0
while pq:
dist, node = heapq.heappop(pq)
if node == end:
return dist
if dist > distances[node]:
continue
for neighbor, weight in graph[node]:
if (new_dist := dist + weight) < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return -1
# Чтение входных данных
N, M = map(int, input().split())
graph = {i: [] for i in range(1, N + 1)}
for _ in range(M):
a, b, w = map(int, input().split())
graph[a].append((b, w))
graph[b].append((a, w))
# Вызов алгоритма Дейкстры для нахождения кратчайшего пути
min_cost = dijkstra(graph, 1, N)
# Вывод результата
print(min_cost)
```