Задача:
Автомобилист хочет проехать от города u до города v, по стране с количеством городов n. Известны длины дорог между всеми городами, дороги двухсторонние. Автомобиль имеет ограниченный запас топлива k, в начале пути бак полностью заполнен. Восполнять запас топлива до максимального k он может в некоторых городах по дороге. Нужно посчитать сколько минимум нужно будет сделать заправок по дороге чтобы попасть из города u в город v.
Формат входных данных
Первая строка содержит пять целых чисел: k
— сколько километров может проехать машина без дозаправок, n
— количество городов, m
— количество дорог, u
— номер города начала дороги, и v
— номер города, куда нужно доехать (1 ≤ k ≤ 500, 2 ≤ n ≤ 10 000, 0 ≤ m ≤ 10 000, 1 ≤ u,v, ≤ n, u ≠ v)
.
В следующих m строках задаются дороги. В i-й
из этих строк записаны три числа p_i, q_i, r_i
—
номера двух городов, которые соединяет очередная двухсторонняя дорога, и её длина. (1 ≤ p_i, q_i ≤ n, 1≤ r_i ≤ 10^9)
Следующая строка содержит целое число l
— количество заправок (0 ≤ l ≤ n)
. Наконец, последняя строка содержит l
чисел a_1, a_2, . . . , a_i
— номера городов с заправками в порядке возрастания (1 ≤ a_1 < a_2 < ... < a_l ≤ n)
.
Формат выходных данных
Выведите -1
, если невозможно доехать от города с номером u
до города с
номером v
, или минимальное количество заправок, если это возможно.
Примеры:
input #1:
3 3 3 1 3
1 2 3
1 3 4
2 3 3
2
2 3
output #1:
1
input #2:
3 3 3 1 3
1 2 2
1 3 4
2 3 2
0
output #2:
-1
input #3:
3 3 3 1 3
1 2 2
1 3 4
2 3 1
0
output #3:
0
Ограничение по времени: 2 секунды;
Ограничение по памяти: 512 мегабайт
Моё решение:
k,n,m,u,v = [int(i) for i in input().split()]
adj = {}
for j in range(m):
p,q,r = [int(i) for i in input().split()]
if p-1 in adj:
adj[p-1].append([q-1,r])
else:
adj[p-1] = [[q-1,r]]
if q-1 in adj:
adj[q-1].append([p-1,r])
else:
adj[q-1] = [[p-1,r]]
l = int(input())
refills = [False] * n
if not l is 0:
for i in input().split():
refills[int(i)-1] = True
count = [0] * n
tank = [None] * n
level = [-1] * n
def bfs(s):
global level,charging,k
level[s] = 0
queue = [s]
tank[s] = k
while queue:
v = queue.pop(0)
for w_ in adj[v]:
w = w_[0]; r = w_[1];
if tank[w] is None:
tank[w] = k
if level[w] is -1 and r<=tank[v]:
level[w] = r+level[v]
if refills[w]:
tank[w] = k
count[w]+=1
else:
tank[w] -=r
queue.append(w)
bfs(u-1)
if level[v-1] is -1:
print(-1)
else:
print(count[v-1])
Я использую поиск в ширину с дополнительными условиями, алгоритм достаточно прост. Но моё решение выдаёт ошибки на некоторых тестах (входные данные на которых происходит ошибка я не знаю).
Подскажите, пожалуйста, что не так в алгоритме. Либо посоветуйте иной способ решения.