Задача #4395
Обход графа
(Л. Шастин) В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M – номера вершин графа, W – вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите путь из вершины с номером 102 в вершину с номером 2616, состоящий из минимального количества рёбер. Укажите в ответе сумму весов всех рёбер, составляющих этот путь. Если таких путей несколько, выберите тот, в котором сумма меньше. Существование хотя бы одного такого пути гарантируется.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. L ≤ 10000, M ≤ 10000; W ≤ 100. Количество строк в файле не превосходит 100 000. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.
Типовой пример организации данных во входном файле для графа на рисунке.
100 12 1.0
6 7 7.0
6 1 1.0
1 7 5.5
7 100 2.0
4 100 8.0
1 100 12.0
1 4 2.5
При условии поиска пути с минимальным числом ребер из вершины с номером 1 в вершину с номером 12, для приведённого примера верным ответом будет 13.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла
Решение
Ответ
def deikstra(st, fn):
d = [[float('inf')] * 2 for _ in range(10_001)]
d[st] = [0] * 2
determined = set()
while fn not in determined:
curr = min([v for v in set(range(1, 10_001)) - determined], key=lambda x: d[x])
determined.add(curr)
for nxt, w in g.get(curr, []):
d[nxt] = min(d[nxt], [d[curr][0] + 1, d[curr][1] + w])
return d[fn][1] / 100
g = {}
for l in open('23_4395.txt'):
u, v, w = l.split()
g.setdefault(int(u), []).append((int(v), float(w) * 100))
print(int(deikstra(102, 2616)))