1 class UnionFind: 2 def __init__(self, elements): 3 self.parent = {} 4 for e in elements: 5 self.parent[e] = e 6 7 def find(self, u): 8 if self.parent[u] != u: 9 self.parent[u] = self.find(self.parent[u]) 10 return self.parent[u] 11 12 def union(self, u, v): 13 root_u = self.find(u) 14 root_v = self.find(v) 15 if root_u != root_v: 16 self.parent[root_u] = root_v 17 18 n = int(input()) 19 edges = [] 20 for _ in range(n-1): 21 parts = input().split() 22 start = parts[0] 23 k = int(parts[1]) 24 ptr = 2 25 for _ in range(k): 26 end = parts[ptr] 27 weight = int(parts[ptr+1]) 28 edges.append((weight, start, end)) 29 ptr += 2 30 31 edges.sort() 32 nodes = [chr(ord('A') + i) for i in range(n)] 33 uf = UnionFind(nodes) 34 total = 0 35 count = 0 36 37 for edge in edges: 38 weight, u, v = edge 39 root_u = uf.find(u) 40 root_v = uf.find(v) 41 if root_u != root_v: 42 uf.union(u, v) 43 total += weight 44 count += 1 45 if count == n - 1: 46 break 47 48 print(total)
This code is an implementation of Dijkstra's algorithm to find the shortest path between locations in a graph. Here is an analysis of the code:
1. Input Handling: The code takes input for the number of locations `P`, the locations themselves, the number of edges `Q`, edge weights, the number of queries `R`, and query destinations.
2. Data Structures:
- `locations`: A list to store the input locations.
- `map_dict`: A dictionary to map each location to its index in the sorted `locations` list.
- `edges`: A list of lists to store edges between nodes.
- `graph`: A 2D list to represent the weighted graph.
3. Setting up the Graph:
- The code populates the `edges` and `graph` lists after processing the input.
- Edge weights are stored in `graph` and adjacent nodes in `edges`.
4. Dijkstra's Algorithm:
- The `dijkstra` function implements Dijkstra's algorithm to find the shortest path between a start and target location.
- It uses a priority queue to store nodes by distance and updates the shortest path as necessary.
- It also tracks the previous node to reconstruct the path once the target is reached.
5. Processing Queries:
- For each query, the code finds the shortest path between the given start and target locations.
- It then prints the path using location names and edge weights.
Overall, this code efficiently finds the shortest path between locations using Dijkstra's algorithm and prints the path for each query. The input data is processed to build the graph representation, and the algorithm is used to find the optimal route.
1 import heapq 2 3 P = int(input()) 4 locations = [] 5 for _ in range(P): 6 locations.append(input()) 7 locations.sort() 8 map_dict = {char: i for i, char in enumerate(locations)} 9 10 edges = [[] for _ in range(P)] 11 graph = [[0 for _ in range(P)] for _ in range(P)] 12 13 Q = int(input()) 14 for _ in range(Q): 15 a, b, c = input().split() 16 c = int(c) 17 u, v = map_dict[a], map_dict[b] 18 edges[u].append((v, c)) 19 edges[v].append((u, c)) 20 graph[u][v] = c 21 graph[v][u] = c 22 23 def dijkstra(start, target): 24 INF = 10**18 25 dist = [INF] * P 26 prev = [-1] * P 27 dist[start] = 0 28 pq = [(0, start)] 29 30 while pq: 31 d, u = heapq.heappop(pq) 32 if d != dist[u]: 33 continue 34 if u == target: 35 break 36 for v, w in edges[u]: 37 nd = d + w 38 if nd < dist[v]: 39 dist[v] = nd 40 prev[v] = u 41 heapq.heappush(pq, (nd, v)) 42 43 if dist[target] == INF: 44 return None, [] 45 path = [] 46 cur = target 47 while cur != -1: 48 path.append(cur) 49 cur = prev[cur] 50 path.reverse() 51 return dist[target], path 52 53 R = int(input()) 54 for _ in range(R): 55 a, b = input().split() 56 start = map_dict[a] 57 target = map_dict[b] 58 59 cost, path = dijkstra(start, target) 60 61 62 if len(path) == 1: 63 print(locations[path[0]]) 64 continue 65 66 for i in range(len(path) - 1): 67 u, v = path[i], path[i+1] 68 print(f'{locations[u]}->({graph[u][v]})->', end='') 69 print(f'{locations[path[-1]]}')
1 from collections import deque 2 3 moves = [ 4 [0, 1, 3, 4], 5 [0, 1, 2], 6 [1, 2, 4, 5], 7 [0, 3, 6], 8 [1, 3, 4, 5, 7], 9 [2, 5, 8], 10 [3, 4, 6, 7], 11 [6, 7, 8], 12 [4, 5, 7, 8] 13 ] 14 15 def bfs(initial_state): 16 queue = deque([(initial_state, [])]) 17 visited = set() 18 visited.add(tuple(initial_state)) 19 while queue: 20 state, move_seq = queue.popleft() 21 if all(s == 0 for s in state): 22 return move_seq 23 for i in range(9): 24 new_state = list(state) 25 for clock_index in moves[i]: 26 new_state[clock_index] = (new_state[clock_index] + 1) % 4 27 if tuple(new_state) not in visited: 28 visited.add(tuple(new_state)) 29 queue.append((new_state, move_seq + [i + 1])) 30 return [] 31 32 initial_state = [] 33 for i in range(3): 34 row = list(map(int, input().split())) 35 initial_state.extend(row) 36 result = bfs(initial_state) 37 print(" ".join(map(str, result)))