Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # -*- coding: utf-8 -*-
- def deikstra(start_node, finish_node, length, matrix):
- result = 0
- current_node = start_node
- distance = {str(i): float('inf') for i in range(1, length + 1)}
- visited = []
- state = [0]*(length + 1) # состоние 1 - подъем 0 - опускание
- distance[str(current_node)] = 0
- while finish_node not in visited:
- visited.append(current_node)
- for arr in matrix[current_node]:
- n = arr[0]
- w = arr[1]
- if n in visited:
- continue
- if distance[str(current_node)] + abs(state[current_node] - w) < distance[str(n)]:
- diff = 0 if current_node == start_node else abs(state[current_node] - w)
- distance[str(n)] = distance[str(current_node)] + diff
- state[n] = w
- minWeight = 19000000
- for i in range(1, length + 1):
- if (i not in visited) and (distance[str(i)] < minWeight):
- current_node = i
- minWeight = distance[str(i)]
- return distance[str(finish_node)]
- n, m = [int(i) for i in input().split()] # n - кол-во вершин, m - кол-во ребер
- graph = {}
- for i in range(m):
- first, last = [int(i) for i in input().split()]
- if first not in graph:
- graph[first] = []
- if last not in graph:
- graph[last] = []
- graph[first].append([last, 1])
- graph[last].append([first, 0])
- start_node, last_node = [int(i) for i in input().split()]
- print(deikstra(start_node, last_node, n, graph))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement