主題
Description:
There is an undirected weighted graph with n vertices labeled from 0 to n - 1.
You are given the integer n and an array edges, where edges[i] = [ui, vi, wi] indicates that there is an edge between vertices ui and vi with a weight of wi.
A walk on a graph is a sequence of vertices and edges. The walk starts and ends with a vertex, and each edge connects the vertex that comes before it and the vertex that comes after it. It's important to note that a walk may visit the same edge or vertex more than once.
The cost of a walk starting at node u and ending at node v is defined as the bitwise AND of the weights of the edges traversed during the walk. In other words, if the sequence of edge weights encountered during the walk is w0, w1, w2, ..., wk, then the cost is calculated as w0 & w1 & w2 & ... & wk, where & denotes the bitwise AND operator.
You are also given a 2D array query, where query[i] = [si, ti]. For each query, you need to find the minimum cost of the walk starting at vertex si and ending at vertex ti. If there exists no such walk, the answer is -1.
Return the array answer, where answer[i] denotes the minimum cost of a walk for query i.
思考：
Graph，我沒看懂它是怎麼走的(為什麼要走過去再走回來)
直接看解答了
=====
Graph一直是我很弱的主題，通常會不知道怎麼動
讀過一遍解答，只看懂了AND的部分，沒看懂怎麼遍歷(畢竟我也沒看懂為什麼描述中為什麼要那樣走)
暫時不是最優先要提升的演算法部分，但可能暑假那附近會試著加強看看
class Solution:
def minimumCost(self, n, edges, queries):
# Create the adjacency list of the graph
adj_list = [[] for _ in range(n)]
for edge in edges:
adj_list[edge[0]].append((edge[1], edge[2]))
adj_list[edge[1]].append((edge[0], edge[2]))
visited = [False] * n
# Array to store the component ID of each node
components = [0] * n
component_cost = []
component_id = 0
# Perform BFS for each unvisited node to identify components and calculate their costs
for node in range(n):
if not visited[node]:
# Get the component cost and mark all nodes in the component
component_cost.append(
self._get_component_cost(
node, adj_list, visited, components, component_id
)
)
component_id += 1
result = []
for query in queries:
start, end = query
if components[start] == components[end]:
# If they are in the same component, return the precomputed cost for the component
result.append(component_cost[components[start]])
else:
# If they are in different components, return -1
result.append(-1)
return result
# Helper function to calculate the cost of a component using BFS
def _get_component_cost(
self, source, adj_list, visited, components, component_id
):
nodes_queue = deque()
# Initialize the component cost to the number that has only 1s in its binary representation
component_cost = -1
nodes_queue.append(source)
visited[source] = True
# Perform BFS to explore the component and calculate the cost
while nodes_queue:
node = nodes_queue.popleft()
# Mark the node as part of the current component
components[node] = component_id
# Explore all neighbors of the current node
for neighbor, weight in adj_list[node]:
# Update the component cost by performing a bitwise AND of the edge weights
component_cost &= weight
# If the neighbor hasn't been visited, mark it as visited and add it to the queue
if visited[neighbor]:
continue
visited[neighbor] = True
nodes_queue.append(neighbor)
return component_cost
