Статья Автор: Деникина Мария

23

dist, vs= {}, set() #dist - растояние м/у вершинами, vs - вершины
for s in open('graf9.txt'):
    a, b, d = s.split()
    dist[(a, b)] =float(d)
    vs.add(a)
    vs.add(b)

k = 1
x = 1
y = 100
while k > 0:
    k = 0
    for b in vs:
        edge = [(a, c) for a in vs for c in vs if (a, b) in dist and (b, c) in dist]
        for a, c in edge:
            d = dist[(a, b)] + dist[(b, c)]
            if (a, c) not in dist or dist[(a, c)] > d:
                dist[(a, c)] = d
                k += 1

'''
В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке записаны два натуральных числа L, M и положительное вещественное число W. Такая строка описывает ребро, ведущее из вершины L в вершину M и имеющее вес W.
Количество строк равно количеству рёбер. Между одной и той же парой вершин нет нескольких рёбер одного направления. Строки с количеством вершин или рёбер в начале файла нет. Номера вершин могут идти не подряд; их числовой порядок не задаёт направление рёбер.
Длина пути равна сумме весов входящих в него рёбер. Найдите целую часть длины длиннейшего пути из вершины 11 в вершину 907. Существование хотя бы одного такого пути гарантируется.
Номера вершин не превышают 1000, вес ребра не превышает 10 000. Количество строк файла не превышает 200. Числа в строках разделены пробелами и/или символами табуляции. Десятичный разделитель — точка. Для выполнения задания следует написать программу.
'''
dist, vs= {}, set() #dist - растояние м/у вершинами, vs - вершины
for s in open('23_02.txt'):
    a, b, d = s.split()
    dist[(a, b)] =float(d)
    vs.add(a)
    vs.add(b)

vs = sorted(vs)
k = 1
x = '11'
y = '907'
p = []
while k > 0:
    k = 0
    for b in vs:
        edge = [(a, c) for a in vs for c in vs if (a, b) in dist and (b, c) in dist]
        for a, c in edge:
            d = dist[(a, b)] + dist[(b, c)]
            if (a, c) not in dist or dist[(a, c)] < d: #< тк ищем max
                dist[(a, c)] = d
                k += 1
                if (x, y) == (a, c):
                    p.append(dist[(a, c)])
print(int(max(p)))

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать