Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.87 KB | None | 0 0
  1. intervals = eval(input())
  2.  
  3. def count_general_waiting_time(red_light_duration, green_light_duration):
  4.     return red_light_duration / (red_light_duration + green_light_duration) * (red_light_duration) / 2
  5.  
  6. def Dijkstra(N, matrix):
  7.     d = [100000] * N        #Массив расстояний до каждого узла, заполняем большими числами
  8.     U = [0] * N             #Маркеры. 0 - ещё не посещали узел, 1 - посещали узел
  9.     d[0] = 0                #Расстояние до нулевого узла равно 0
  10.     d_min = 1000000        
  11.     p = ['']*N              #Это будет нужная нам строка направлений
  12.     while U.count(0) != 0:  #Проверяем, остались ли ещё непосещенные узлы
  13.         d_min = 1000000
  14.         for i in range(N):                                           #Выбираем самый близкий из непосещённых узлов тот
  15.             if U[i] == 0 and d[i] < d_min:
  16.                 d_min = d[i]
  17.                 ID_min = i
  18.         for k in range(N):                                           #Пробегаем все остальные узлы
  19.             if U[k] == 0 and d[k] > d[ID_min] + matrix[ID_min][k]:   #И выбираем только те их них, которые мы не посетили и до которых ближе идти от узлы ID_min    
  20.                 d[k] = d[ID_min] + matrix[ID_min][k]                 #Если так ближе, то перезапишем расстояние и запишем маршрут до него
  21.                 if k - ID_min == 1:
  22.                     p[k] = p[ID_min] + 'r'
  23.                 elif k - ID_min == -1:
  24.                     p[k] = p[ID_min] + 'l'
  25.                 elif k - ID_min > 1:
  26.                     p[k] = p[ID_min] + 'd'
  27.                 elif k - ID_min < -1:
  28.                     p[k] = p[ID_min] + 'u'
  29.                 if ID_min == 0:                #Это условие нужно для того, чтобы пропустить переход от первого узла
  30.                     d[k] = 0
  31.         U[ID_min] = 1;
  32.     print(d[N-1])
  33.     return p[N-1]
  34.  
  35. N = len(intervals) * len(intervals[0])
  36. matrix = [[1000000] * N for i in range(N)]
  37.  
  38.  
  39. for y in range(len(intervals)):                             #Переводим входные данные в матрицу матрицу смежности
  40.     for x in range(len(intervals[0])):
  41.         if y - 1 >= 0:
  42.             matrix[len(intervals[0])*(y-1)+x][len(intervals[0])*(y)+x] = count_general_waiting_time(intervals[y-1][x][0],intervals[y-1][x][2])
  43.             matrix[len(intervals[0])*(y)+x][len(intervals[0])*(y-1)+x] = count_general_waiting_time(intervals[y][x][0],intervals[y][x][2])
  44.  
  45.         if y + 1 < len(intervals):
  46.             matrix[len(intervals[0])*(y)+x][len(intervals[0])*(y+1)+x] = count_general_waiting_time(intervals[y][x][0],intervals[y][x][2])
  47.             matrix[len(intervals[0])*(y+1)+x][len(intervals[0])*(y)+x] = count_general_waiting_time(intervals[y+1][x][0],intervals[y+1][x][2])
  48.  
  49.         if x - 1 >= 0:
  50.             matrix[len(intervals[0])*(y)+x-1][len(intervals[0])*(y)+x] = count_general_waiting_time(intervals[y][x-1][0],intervals[y][x-1][1])
  51.             matrix[len(intervals[0])*(y)+x][len(intervals[0])*(y)+x-1] = count_general_waiting_time(intervals[y][x][0],intervals[y][x][1])
  52.            
  53.         if x + 1 < len(intervals[0]):
  54.             matrix[len(intervals[0])*(y)+x][len(intervals[0])*(y)+x+1] = count_general_waiting_time(intervals[y][x][0],intervals[y][x][1])
  55.             matrix[len(intervals[0])*(y)+x+1][len(intervals[0])*(y)+x] = count_general_waiting_time(intervals[y][x+1][0],intervals[y][x+1][1])
  56.  
  57. trace = Dijkstra(N, matrix) #Вызываем функцию Дейкстры
  58. print (trace)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement