Участник:Krivosheev.ah/MICEMAZE

Материал из DISCOPAL
Перейти к: навигация, поиск

Python3

https://www.spoj.com/problems/MICEMAZE/

def warshall(adjMat, n):
    dp = adjMat
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dp[i][k] + dp[k][j] < dp[i][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]
    return dp
 
def main():
    n = input()
    n = int(n)
    e = input()
    e = int(e)
    t = input()
    t = int(t)
    m = input()
    m = int(m)
    maze = [[float('inf')]*n for _ in range(n)]
 
    for x in range(m):
        text = input().split()
        a = int(text[0])
        b = int(text[1])
        w = int(text[2])
        maze[a - 1][b - 1] = w
 
    paths = warshall(maze, n)
    paths[e - 1][e - 1] = 0
    count = 0
 
    for x in range(n):
        if paths[x][e - 1] <= t:
            count += 1
    print(count)
 
main()