Miscellany

from sys import stdinfrom math import log10, powInf = float(1e3000)class Node:	forgjenger = -1	estimat = Inf	kjent = False	nummer = 0	naboer = None		def __init__(self, node):		self.nummer = node		def main():	n = int(stdin.readline())	sannsynligheter = [float(x) for x in stdin.readline().split()]	nodeliste = [None] * n	ko = [None] * n	nodenr = 0		for linje in stdin:		nodeliste[nodenr] = Node(nodenr)		nodeliste[nodenr].naboer = [int(nabo) for nabo in linje.split()]		ko[nodenr] = nodeliste[nodenr]		nodenr += 1		if (sannsynligheter[0] == 0) or (sannsynligheter[n-1] == 0):		print "%.3f" % (0 + 1E-12)		else:				antKjenteNoder = 0		nodeliste[0].estimat = -log10(sannsynligheter[0])		antIt = int(n/2)+2 #trenger bare sjekke halve grafen paa grunn av uretta (+2 for aa forsikre at int(n/2) + 1		                   #iterasjoner blir foretatt dersom d er et odde antall noder ;P		                   		while (antKjenteNoder < antIt):						#prioritets que			minste = Inf			behandlernode = None			teller = 0			koindeks = 0						for node in ko:				if node.estimat < minste:					koindeks = teller					behandlernode = node					minste = node.estimat				teller += 1								#dersom den minste tilgjenglige noden ikke har estimat				if behandlernode == None:				break						ko.pop(koindeks)						behandlernode.kjent = True			antKjenteNoder += 1						#behandlernode er naa naermest			for nabo in behandlernode.naboer:				if not nodeliste[nabo].kjent: 					if not (sannsynligheter[nabo] == 0):						#print nodeliste[behandlernode.nummer].estimat						nyttEstimat = nodeliste[behandlernode.nummer].estimat - log10(sannsynligheter[nabo])						if nodeliste[nabo].estimat > nyttEstimat:							#oppdater							nodeliste[nabo].estimat = nyttEstimat							nodeliste[nabo].forgjenger = behandlernode.nummer							#beregn sannsynlighet				noden = nodeliste[n-1] #sluttnoden		sannsynlighet = pow(10,-noden.estimat)				print "%.3f" % (sannsynlighet + 1E-12)		main()