forked from ngiengkianyew/daily-coding-problem
-
Notifications
You must be signed in to change notification settings - Fork 0
/
problem_294.py
56 lines (42 loc) · 1.43 KB
/
problem_294.py
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
import sys
def get_shortest_path(
target, elevations, path_map, path_so_far,
elevations_so_far, distance, switches):
if 0 == target and path_so_far:
return path_so_far, distance if switches < 2 else sys.maxsize
min_dist, min_path = sys.maxsize, None
for src, dist in path_map[target]:
if src == target:
continue
new_switches = switches + 1 \
if elevations_so_far and elevations[src] > elevations_so_far[0] \
else switches
new_path_so_far, new_dist = get_shortest_path(
src, elevations, path_map, [src] + path_so_far,
[elevations[target]] + elevations_so_far, distance + dist, new_switches)
if new_dist < min_dist:
min_dist = new_dist
min_path = new_path_so_far
return min_path, min_dist
def get_shortest_path_helper(elevations, paths):
path_map = dict()
for (src, tgt), dist in paths.items():
if tgt not in path_map:
path_map[tgt] = list()
path_map[tgt].append((src, dist))
shortest_path, _ = get_shortest_path(
0, elevations, path_map, list(), list(), 0, 0)
return shortest_path
# Tests
elevations = {0: 5, 1: 25, 2: 15, 3: 20, 4: 10}
paths = {
(0, 1): 10,
(0, 2): 8,
(0, 3): 15,
(1, 3): 12,
(2, 4): 10,
(3, 4): 5,
(3, 0): 17,
(4, 0): 10,
}
assert get_shortest_path_helper(elevations, paths) == [0, 2, 4]