-
Notifications
You must be signed in to change notification settings - Fork 0
/
#41.py
59 lines (39 loc) · 1.13 KB
/
#41.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
57
58
59
def flight_itinerary(flights, start):
connections = {}
for connection in flights:
strt, dest = connection
if not strt in connections:
connections[strt] = []
connections[strt].append(dest)
def find_path(curr, taken, itinerary):
itinerary.append(curr)
if len(taken) == len(flights):
return itinerary
if not curr in connections.keys():
return None
for dest in connections[curr]:
if not (curr, dest) in taken:
temp = taken.copy()
temp.add((curr, dest))
ret = find_path(dest, temp, itinerary)
if ret is not None:
return ret
return None
return find_path(start, set(), [])
n = int(input("Number of (origin, destination) pairs: "))
flights = []
for i in range(n):
pair = input().split(' ')
flights.append(pair)
origin = input("Origin: ")
itinerary = flight_itinerary(flights, origin)
if itinerary is None:
print("No itinerary possible.")
else:
output = "Itinerary: "
for i in range(len(itinerary)):
if i == len(itinerary) - 1:
output = output + itinerary[i]
else:
output = output + itinerary[i] + " -> "
print(output)