coding utf-8 Профессору Форду необходимо попасть на международную конф

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
# -*- coding: utf-8 -*-
"""
Профессору Форду необходимо попасть на международную конференцию.
Он хочет потратить на дорогу наименьшее количество денег, поэтому
решил, что будет путешествовать исключительно ночными авиарейсами
(чтобы не тратиться на ночевку в отелях), а днем будет осматривать
достопримечательности тех городов, через которые он будет проезжать
транзитом. Он внимательно изучил расписание авиаперелетов и составил
набор подходящих авиарейсов, выяснив, что перелеты на выбранных
направлениях совершаются каждую ночь и за одну ночь он не сможет
совершить два перелета.
Теперь профессор хочет найти путь наименьшей стоимости, учитывая что
до конференции осталось K ночей (то есть профессор может совершить
не более K перелетов).
В первой строке находятся числа N (количество городов), M (количество
авиарейсов), K (количество оставшихся ночей), S (номер города, в
котором живет профессор), F (номер города, в котором проводится
конференция). Ограничения:
2 <= N <= 100, 1 <= M <= 105, 1 <= K <= 100, 1 <= S <= N, 1 <= F <= N.
Далее идет M строк, задающих расписание авиарейсов. i-я строка содержит
три натуральных числа: Si, Fi и Pi, где Si - номер города, из которого
вылетает i-й рейс, Fi - номер города, в который прилетает i-й рейс,
Pi - стоимость перелета i-м рейсом. 1<=Si<=N, 1<=Fi<=N, 1<=Pi<=10^6.
Выведите одно число - минимальную стоимость пути, подходящего для
профессора. Если профессор не сможет за K ночей добраться до
конференции, выведите число -1.
ВВОД ВЫВОД
4 5 2 1 4
1 2 1
2 3 1
3 4 1
1 3 3
1 4 5 4
"""
N, M, K, S, F = map(int, input().split())
INF = float('inf')
P = [INF] * (N + 1)
P[S] = 0; Edges = []
for i in range(M):
Edges.append(list(map(int, input().split())))
for i in range(K):
Pnew = P[:]
for start, end, price in Edges:
if P[start] + price < Pnew[end]:
Pnew[end] = P[start] + price
P = Pnew
if P[F] == INF: print(-1)
else: print(P[F])
'''
INF = float('inf')
n, m, k, s, f = map(int,input().split())
e = []; d = [INF]*(n+1); p = [INF]*(n+1)
for i in range(m):
e.append(list(map(int,input().split())))
d[s] = 0; p[s] = 0
for j in range(k):
for i in range(m):
if d[e[i][0]] < INF:
if d[e[i][1]] > d[e[i][0]] + e[i][2]:
p[e[i][1]] = d[e[i][0]] + e[i][2]
for i in range(1,n+1): d[i] = p[i]
if d[f] == INF: print(-1)
else: print(d[f])
'''