fork download
copy 
  1. from collections import deque
  2.  
  3. def nearest_meeting_cell(n, edges, c1, c2):
  4.     def bfs(start):
  5.         """BFS to calculate shortest distance from the start node."""
  6.         distances = {}
  7.         queue = deque([(start, 0)])  # (current node, current distance)
  8.         visited = set()
  9.  
  10.         while queue:
  11.             node, dist = queue.popleft()
  12.             if node in visited:  # Skip already visited nodes
  13.                 continue
  14.             visited.add(node)
  15.             distances[node] = dist
  16.  
  17.             # Traverse to the next node if it exists and is unvisited
  18.             next_node = edges[node]
  19.             if next_node != -1 and next_node not in visited:
  20.                 queue.append((next_node, dist + 1))
  21.  
  22.         return distances
  23.  
  24.     # Step 1: Get distances from C1 and C2
  25.     dist_from_c1 = bfs(c1)
  26.     dist_from_c2 = bfs(c2)
  27.  
  28.     # Step 2: Find common cells reachable from both C1 and C2
  29.     common_cells = set(dist_from_c1.keys()) & set(dist_from_c2.keys())
  30.  
  31.     if not common_cells:
  32.         return -1  # No common meeting cell
  33.  
  34.     # Step 3: Find the nearest meeting cell with the smallest max distance
  35.     nearest_cell = -1
  36.     min_distance = float('inf')
  37.  
  38.     for cell in common_cells:
  39.         total_distance = max(dist_from_c1[cell], dist_from_c2[cell])
  40.         if total_distance < min_distance:
  41.             min_distance = total_distance
  42.             nearest_cell = cell
  43.  
  44.     return nearest_cell
  45.  
  46. # Input Parsing
  47. if __name__ == "__main__":
  48.     n = int(input("Enter the number of cells (N): "))  # Number of cells
  49.     edges = list(map(int, input("Enter the edges array: ").split()))  # Edges array
  50.     c1, c2 = map(int, input("Enter the two cells (C1 and C2): ").split())  # Query cells
  51.  
  52.     # Output the nearest meeting cell
  53.     result = nearest_meeting_cell(n, edges, c1, c2)
  54.     print(f"Nearest Meeting Cell: {result}")
  55.  
Success #stdin #stdout 0.03s 9792KB
comments (?)
stdin
copy 
23
4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21
9 2
stdout
copy 
Enter the number of cells (N): Enter the edges array: Enter the two cells (C1 and C2): Nearest Meeting Cell: 4
https://ideone.com/AytEDv
language:
Python 3 (python  3.9.5)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!