Задание 23

Графы и пути

Типов: 2

Как распознать

Файл содержит ориентированные рёбра L M W с положительным весом.

Условие

Найти целую часть кратчайшего пути из вершины 1 в 100.

Разбор

Многократно ослабляй расстояния по всем рёбрам ациклического графа.

Шаблон

file = open('demo_23.txt')
data = []
for line in file:
    a, b, l = line.split()
    data.append([int(a), int(b), float(l)])

dist = [float('inf')] * 1001
dist[1] = 0
for i in range(len(data)):
    for a, b, l in data:
        dist[b] = min(dist[b], dist[a] + l)
print(int(dist[100]))

Как распознать

Ориентированный ациклический взвешенный граф.

Условие

По файлу 23.txt найти целую часть кратчайшего пути из 3 в 97.

Разбор

Используй тот же многократный проход по рёбрам.

Шаблон

file = open('23.txt')
data = []
for line in file:
    a, b, l = line.split()
    data.append([int(a), int(b), float(l)])
dist = [float('inf')] * 1001
dist[3] = 0
for i in range(len(data)):
    for a, b, l in data:
        dist[b] = min(dist[b], dist[a] + l)
print(int(dist[97]))