def findCheapestPrice(n, flights, src):
MAX = 1000000
graph = [[MAX] * n for _ in range(n)]
visited = [False] * n
dist = [MAX] * n
dist[src] = 0
for u, v, w in flights:
graph[u][v] = w
if u == src:
dist[v] = w
visited[src] = True
for _ in range(n - 1):
min_v = MAX
min_id = None
for j in range(n):
if not visited[j] and dist[j] < min_v:
min_v = dist[j]
min_id = j
visited[min_id] = True
for i in range(n):
if not visited[i] and graph[min_id][i] != MAX and dist[min_id] + graph[min_id][i] < dist[i]:
dist[i] = dist[min_id] + graph[min_id][i]
return graph[0]
n = 4
flights = [[0,1,10],[1,2,10],[0,2,30], [1,3,5], [3,2,3]]
src= 0
dst =2
print(findCheapestPrice(n, flights, src))
|