Advertisement
Guest User

Untitled

a guest
May 22nd, 2019
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.87 KB | None | 0 0
  1. def main():
  2.     n = int(raw_input().strip())
  3.     adj = {i: [] for i in xrange(n)}
  4.     for i in xrange(n-1):
  5.         a, b, x, t = map(int, raw_input().strip().split())
  6.         a -= 1
  7.         b -= 1
  8.         x /= 100.0
  9.         t = bool(t)
  10.         adj[a].append((b, x, t))
  11.         adj[b].append((a, x, t))
  12.     req = map(int, raw_input().strip().split())
  13.  
  14.     order = [0]
  15.     pipe = [None] * n
  16.     pipe[0] = 0, 1, False
  17.     for i in xrange(n):
  18.         v = order[i]
  19.         for a, x, t in adj[v]:
  20.             if pipe[a] is not None:
  21.                 continue
  22.             order.append(a)
  23.             pipe[a] = v, x, t
  24.     for i in xrange(n-1, 0, -1):
  25.         v = order[i]
  26.         p, x, t = pipe[v]
  27.         r = req[v]
  28.         if t:
  29.             r = min(r, r**.5)
  30.         req[p] = max(req[p], r/x)
  31.     print '{:.4f}'.format(req[0])
  32.  
  33. if __name__ == '__main__':
  34.     main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement