# Untitled

unknown
plain_text
13 days ago
5.8 kB
5
Indexable
Never
```import heapq

class CityMap:
# Calculate total number of unique locations from roads and tracks
self.total_places = max(max(route[0], route[1]) for route in roads + tracks) + 1

# Setup lists for connections
self.paths_tracks = [[] for _ in range(self.total_places)]
self.paths_roads = [[] for _ in range(self.total_places)]
self.locations_friends = [None] * self.total_places

# Fill in the track paths from the tracks data
for start, end, weight in tracks:
self.paths_tracks[start].append((end, weight))

# Setup road connections, ensuring bi-directional nature
for start, end, weight in roads:

# Map friends to their respective locations
for friend, position in friends:
self.locations_friends[position] = friend

# Initialize distances and previous node trackers for all locations
min_distances = [float('inf')] * self.total_places
path_predecessors = [-1] * self.total_places
min_distances[origin] = 0
priority_queue = [(0, origin)]  # Pair of (distance, location index)

while priority_queue:
current_dist, current_loc = heapq.heappop(priority_queue)

if current_dist > min_distances[current_loc]:
continue  # Skip if a better path has already been found

# Select the appropriate connections based on path type
else:
active_connections = self.paths_tracks

# Update distances for all connected nodes
new_dist = current_dist + weight

return min_distances, path_predecessors

def trace_route(self, route_predecessors, target):
# This function traces back the route from a given target using predecessors array
travel_path = []
step = target
while step != -1:
travel_path.append(step)
step = route_predecessors[step]
return travel_path[::-1]

def search_nearby_stations(self, friend_pos):
# This method identifies all nearby stations from a friend's position within two stops
checked = [False] * self.total_places  # Changed from self.num_locations to self.total_places
process_queue = [(friend_pos, 0)]  # holds tuples of (current position, number of stops)
nearby_stations = []

while process_queue:
place, stops = process_queue.pop(0)
if stops > 2:
break  # limit search to two stops
nearby_stations.append((place, stops))
checked[place] = True

if stops < 2:
for adjacent, _ in self.paths_tracks[place]:  # Ensure you're using the correct paths

return nearby_stations

def plan(self, start, destination):
# Calculate the shortest paths from start to all destinations on roads and tracks
track_distances, _ = self.find_shortest_path(start, "track")

optimal_route = None
minimum_time = float('inf')
optimal_friend = None
optimal_station = None
optimal_stops = float('inf')

# Check each friend's location for possible pickup options
for loc, friend in enumerate(self.locations_friends):  # Changed from self.friend_locations to self.locations_friends
if friend is None:
continue

possible_pickups = self.search_nearby_stations(loc)

for pickup_loc, stops in possible_pickups:
# Determine the best path to destination from the pickup location
track_distances_to_dest, _ = self.find_shortest_path(pickup_loc, "track")

# Combine times from start to pickup and pickup to destination
time_via_track = track_distances[pickup_loc] + track_distances_to_dest[destination]