message: Update reachable-nodes-in-subdivided-graph.py
diff: @@ -52,9 +52,10 @@ class Solution(object):
  :type N: int
  :rtype: int
  """
  - graph = collections.defaultdict(dict)
  + adj = [[] for _ in xrange(N)]
  for u, v, w in edges:
  - graph[u][v] = graph[v][u] = w
  + adj[u].append((v, w))
  + adj[v].append((u, w))
  min_heap = [(0, 0)]
  best = collections.defaultdict(lambda: float("inf"))
  @@ -62,18 +63,17 @@ class Solution(object):
  count = collections.defaultdict(lambda: collections.defaultdict(int))
  result = 0
  while min_heap:
  - curr_total, node = heapq.heappop(min_heap) # O(|V|*log|V|) in total
  - if best[node] < curr_total:
  + curr_total, u = heapq.heappop(min_heap) # O(|V|*log|V|) in total
  + if best[u] < curr_total:
  continue
  result += 1
  - for nei, weight in graph[node].iteritems():
  - count[node][nei] = min(weight,
  - M-curr_total)
  - next_total = curr_total+weight+1
  - if next_total <= M and next_total < best[nei]:
  - heapq.heappush(min_heap, (next_total, nei)) # binary heap O(|E|*log|V|) in total
  + for v, w in adj[u]:
  + count[u][v] = min(w, M-curr_total)
  + next_total = curr_total+w+1
  + if next_total <= M and next_total < best[v]:
  + best[v] = next_total
  + heapq.heappush(min_heap, (next_total, v)) # binary heap O(|E|*log|V|) in total
  # Fibonacci heap O(|E|) in total
  - best[nei] = next_total
  for u, v, w in edges:
  result += min(w, count[u][v]+count[v][u])
  return result
  