PlotnikovPhilipp

Untitled

Nov 17th, 2019
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.42 KB | None | 0 0
  1. def deikstra(current_node, finish_node, length, matrix):
  2.     result = 0
  3.     distance = {str(i): float('inf') for i in range(1, length + 1)}
  4.     visited = []
  5.     state = [0]*(length + 1) # состоние 1 - подъем 0 - опускание
  6.     distance[str(current_node)] = 0
  7.     while finish_node not in visited:
  8.         visited.append(current_node)
  9.         for arr in matrix[current_node]:
  10.             n = arr[0]
  11.             w = arr[1]
  12.             if n in visited:
  13.                 continue
  14.             if distance[str(current_node)] + abs(state[current_node] - w) < distance[str(n)]:
  15.                 distance[str(n)] = distance[str(current_node)] + abs(state[n] - w)
  16.                 state[n] = w
  17.         minWeight = 19000000
  18.         for i in range(1, length + 1):
  19.             if (i not in visited) and (distance[str(i)] < minWeight):
  20.                 current_node = i
  21.                 minWeight = distance[str(i)]
  22.     return distance[str(finish_node)]
  23.  
  24. n, m = [int(i) for i in input().split()] # n - кол-во вершин, m - кол-во ребер
  25. graph = {}
  26. for i in range(m):
  27.     first, last = [int(i) for i in input().split()]
  28.     if first not in graph:
  29.         graph[first] = []
  30.     if last not in graph:
  31.         graph[last] = []
  32.     graph[first].append([last, 1])
  33.     graph[last].append([first, 0])
  34. start_node, last_node = [int(i) for i in input().split()]
  35. print(deikstra(start_node, last_node, n, graph))
Advertisement
Add Comment
Please, Sign In to add comment