Advertisement
PlotnikovPhilipp

Untitled

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