gistfile1.py

cache = dict() # cache[x] is a map from weights to paths s->x
s = 0 # source

def find(t):
  if t in cache: return cache[t]
  if t == s:
    return dict([(0,[s])])
  r = dict()
  for (x, w) in pred(t):
    for (ww, path) in find(x):
      r[w+ww] = cons(t, path)
  return r