Answer to Question #212194 in Python for Fazal

Question

Input format:

The first line contains of 4 space separated integers. N(1<=N<=10^3), M(N-1<=M<=(N(N-1)/2).T(1<=T<=10^3) and c(1<=C<=10^3). Next m line contains two integers each. U and V denoting that there is a bidirectional road between U and V.

Output format :

Print N integers, where i th denotes the number of routes which will take the minimum amount of time required to move from city 1 to city N passing through the city i

Answer 1

def dfs(root, res=None):
    if res is None:
        res = [2 * m] * n
    res[root - 1] = 0
    visited = set()
    stack = [root]
    while stack:
        vertex = stack.pop()
        visited.add(vertex)
        for elem in graph[vertex]:
            if elem not in visited:
                if res[vertex - 1] + 1 < res[elem - 1]:
                    res[elem - 1] = res[vertex - 1] + 1
                stack.append(elem)
    return res


n, m, t, c = map(int, input().split())
graph = {i + 1: [] for i in range(n)}
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
ans = dfs(1)  # the shortest way from city 1 to city i
for i in range(1, n):  # the shortest way from city i to city N
    tmp = dfs(i)
    ans[i - 1] += tmp[-1]
print(*ans)

# Example of input
# 4 4 1 1
# 1 2
# 2 3
# 1 3
# 3 4