Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- intervals = eval(input())
- def count_general_waiting_time(red_light_duration, green_light_duration):
- return red_light_duration / (red_light_duration + green_light_duration) * (red_light_duration) / 2
- def Dijkstra(N, matrix):
- d = [100000] * N #Массив расстояний до каждого узла, заполняем большими числами
- U = [0] * N #Маркеры. 0 - ещё не посещали узел, 1 - посещали узел
- d[0] = 0 #Расстояние до нулевого узла равно 0
- d_min = 1000000
- p = ['']*N #Это будет нужная нам строка направлений
- while U.count(0) != 0: #Проверяем, остались ли ещё непосещенные узлы
- d_min = 1000000
- for i in range(N): #Выбираем самый близкий из непосещённых узлов тот
- if U[i] == 0 and d[i] < d_min:
- d_min = d[i]
- ID_min = i
- for k in range(N): #Пробегаем все остальные узлы
- if U[k] == 0 and d[k] > d[ID_min] + matrix[ID_min][k]: #И выбираем только те их них, которые мы не посетили и до которых ближе идти от узлы ID_min
- d[k] = d[ID_min] + matrix[ID_min][k] #Если так ближе, то перезапишем расстояние и запишем маршрут до него
- if k - ID_min == 1:
- p[k] = p[ID_min] + 'r'
- elif k - ID_min == -1:
- p[k] = p[ID_min] + 'l'
- elif k - ID_min > 1:
- p[k] = p[ID_min] + 'd'
- elif k - ID_min < -1:
- p[k] = p[ID_min] + 'u'
- if ID_min == 0: #Это условие нужно для того, чтобы пропустить переход от первого узла
- d[k] = 0
- U[ID_min] = 1;
- print(d[N-1])
- return p[N-1]
- N = len(intervals) * len(intervals[0])
- matrix = [[1000000] * N for i in range(N)]
- for y in range(len(intervals)): #Переводим входные данные в матрицу матрицу смежности
- for x in range(len(intervals[0])):
- if y - 1 >= 0:
- 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])
- matrix[len(intervals[0])*(y)+x][len(intervals[0])*(y-1)+x] = count_general_waiting_time(intervals[y][x][0],intervals[y][x][2])
- if y + 1 < len(intervals):
- matrix[len(intervals[0])*(y)+x][len(intervals[0])*(y+1)+x] = count_general_waiting_time(intervals[y][x][0],intervals[y][x][2])
- 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])
- if x - 1 >= 0:
- 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])
- matrix[len(intervals[0])*(y)+x][len(intervals[0])*(y)+x-1] = count_general_waiting_time(intervals[y][x][0],intervals[y][x][1])
- if x + 1 < len(intervals[0]):
- matrix[len(intervals[0])*(y)+x][len(intervals[0])*(y)+x+1] = count_general_waiting_time(intervals[y][x][0],intervals[y][x][1])
- 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])
- trace = Dijkstra(N, matrix) #Вызываем функцию Дейкстры
- print (trace)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement