Решите срочно задачу на питоне пожалуйста
Ограничение по времени: 1.8 секунд
Дедушка рассказал, как он ходил в школу.
Дедушка выходил из дома и затем проходил по нескольким переходам между перекрёстками.
Перекрёстки соединены направленными улицами и направленными коридорами внутри зданий, двигаться по таким переходам можно только в одном конкретном направлении. На улице можно замёрзнуть (потерять тепло), а в здании можно согреться (набрать тепло). Дедушка добирался до
школы быстрее некуда, но при этом он никогда не переохлаждался и не перегревался по дороге,
то есть количество тепла всегда было в пределах от −30 до +30 (границы включительно). Перед
началом пути количество тепла у дедушки всегда было равно нулю.
Дедушка не помнит конкретный путь, но помнит n пронумерованных от 1 до n перекрёстков, по
которым он мог идти, и m переходов между ними. Про каждый переход (это может быть как улица,
так и коридор) дедушка помнит, из какого перекрёстка к какому этот переход вёл, сколько времени
требовалось, чтобы его пройти, и сколько тепла дедушка терял (в случае улицы) или приобретал (в
случае коридора) при проходе по нему.
Помогите дедушке вспомнить, за какое минимальное время он добирался до школы или скажите,
что дедушка что-то забыл и добраться от дома до школы без переохлаждения и без перегрева при
заданном наборе перекрёстков и переходов невозможно.
Формат входных данных
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно
целое число t (1 6 t 6 10 000) — количество наборов входных данных. Далее следует описание
наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа n, m
(1 6 n, m 6 105
) — количество перекрёстков и количество переходов между ними.
i-я из последующих m строк содержит 4 целых числа u, v, l и dt (1 6 u, v 6 n, u 6= v, 1 6 l 6 106
,
−30 6 dt 6 30), которые означают существование перехода, по которому дедушка мог пройти за
время l от перекрёстка u к перекрёстку v с изменением тепла на dt при проходе по нему. Если
dt < 0, то данный переход — это улица и дедушка терял −dt тепла при проходе по нему, иначе
данный переход — это коридор здания и дедушка приобретал dt тепла при проходе по нему.
Выходя из дома, дедушка моментально попадал на перекрёсток под номером 1. А в школу дедушка моментально входил, как только оказывался на перекрёстке номер n.
Гарантируется, что сумма n (и сумма m) по всем наборам входных данных не превосходит 105
.
Возможно, что от некоторого перекрёстка u к некоторому перекрёстку v ведёт несколько переходов или что существует одновременно переход от u к v и переход от v к u.
Формат выходных данных
Для каждого теста выведите единственное число — минимальное время, за которое дедушка
добирался от дома до школы. Если добраться до школы без переохлаждения и без перегрева невозможно, то выведите −1.
import heapq
def solve():
n, m = map(int, input().split())
edges = []
for _ in range(m):
u, v, l, dt = map(int, input().split())
edges.append((u, v, l, dt))
dist = {}
dist[(1, 0)] = 0
pq = [(0, 1, 0)]
while pq:
d, u, heat = heapq.heappop(pq)
if u == n:
print(d)
return
if d > dist.get((u, heat), float('inf')):
continue
for from_u, to_v, time, delta_heat in edges:
if from_u == u:
new_heat = heat + delta_heat
if -30 <= new_heat <= 30:
new_dist = d + time
if new_dist < dist.get((to_v, new_heat), float('inf')):
dist[(to_v, new_heat)] = new_dist
heapq.heappush(pq, (new_dist, to_v, new_heat))
print(-1)
t = int(input())
for _ in range(t):
solve() это все на своём питоне надо ручкой написать? ну и извращенцы же программисты
import heapq
def dijkstra_with_temperature(n, m, edges):
# Граф представлен в виде списка смежности
graph = [[] for _ in range(n)]
for u, v, l, dt in edges:
graph[u - 1].append((v - 1, l, dt))
# Приоритетная очередь для алгоритма Дейкстра
pq = [(0, 0, 0)] # (время, перекресток, тепло)
# Массивы для хранения минимального времени и тепла
min_time = [[float('inf')] * 61 for _ in range(n)]
min_temp = [[float('inf')] * 61 for _ in range(n)]
min_time[0][30] = 0
while pq:
time, u, temp = heapq.heappop(pq)
if u == n - 1:
return time
for v, l, dt in graph[u]:
new_time = time + l
new_temp = temp + dt
if new_temp < -30 or new_temp > 30:
continue
if new_time < min_time[v][new_temp + 30]:
min_time[v][new_temp + 30] = new_time
min_temp[v][new_temp + 30] = temp
heapq.heappush(pq, (new_time, v, new_temp))
return -1
# Чтение входных данных
import sys
input = sys.stdin.read
data = input().split()
index = 0
t = int(data[index])
index += 1
results = []
for _ in range(t):
n = int(data[index])
m = int(data[index + 1])
index += 2
edges = []
for _ in range(m):
u = int(data[index])
v = int(data[index + 1])
l = int(data[index + 2])
dt = int(data[index + 3])
edges.append((u, v, l, dt))
index += 4
result = dijkstra_with_temperature(n, m, edges)
results.append(result)
# Вывод результатов
for result in results:
print(result)
Потрму что