# visiting all the nodes , adjacent to current node for node,rate in graph[(currency,day)].items(): nextCurrency,nextDay=node if(nextDayamount[node]): heapq.heappush(maxHeap,(-1*nextValue,node)) #print(amount)
return max( amount[(initialCurrency,2)], 1) # # let us say currencies are :A,B,C # in my solution, these will be the nodes: # (A,1),(B,1),(C,1) # representing day1 nodes # (A,2),(B,2),(C,2) # representing day2 nodes
contest link: leetcode.com/contest/weekly-contest-428/
Please let me know, if you need Solutions in Hindi , also.
from collections import defaultdict
import heapq
class Solution:
def maxAmount(self, initialCurrency: str, pairs1: List[List[str]], rates1: List[float], pairs2: List[List[str]], rates2: List[float]) -> float:
graph=defaultdict(lambda:defaultdict(int))
for i in range(len(pairs1)):
fromm,too=pairs1[i]
rate=rates1[i]
graph[(fromm,1)][(too,1)]=rate
graph[(too,1)][(fromm,1)]=1/rate
if(too!=initialCurrency):
graph[(too,1)][(too,2)]=1
if(fromm!=initialCurrency):
graph[(fromm,1)][(fromm,2)]=1
for i in range(len(pairs2)):
fromm,too=pairs2[i]
rate=rates2[i]
graph[(fromm,2)][(too,2)]=rate
graph[(too,2)][(fromm,2)]=1/rate
amount=defaultdict(int)
#print(graph)
# Using Dijkstra's algorithm
maxHeap=[(-1,(initialCurrency,1))]
while(maxHeap):
value,(currency,day)=heapq.heappop(maxHeap)
value*=-1
if(amount[(currency,day)]>value):
continue
#print(currency,day,amount[(currency,day)],value)
amount[(currency,day)]=value
# visiting all the nodes , adjacent to current node
for node,rate in graph[(currency,day)].items():
nextCurrency,nextDay=node
if(nextDayamount[node]):
heapq.heappush(maxHeap,(-1*nextValue,node))
#print(amount)
return max( amount[(initialCurrency,2)], 1)
#
# let us say currencies are :A,B,C
# in my solution, these will be the nodes:
# (A,1),(B,1),(C,1) # representing day1 nodes
# (A,2),(B,2),(C,2) # representing day2 nodes