We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
# Enter your code here. Read input from STDIN. Print output to STDOUT# Problem: https://www.interviewstreet.com/challenges/dashboard/#problem/4f6522ab2f425fromheapqimportheappush,heappopINF=999999999999999classSegTreeNode(object):def__init__(self,left,right,data):self.left=leftself.right=rightself.data=dataself.left_child=Noneself.right_child=Nonedef__repr__(self):return"<node left:%d right:%d data:%d>"%(self.left,self.right,self.data)classSegTree(object):def__init__(self,left,right):self.root=self.make_tree(left,right)defmake_tree(self,left,right):node=SegTreeNode(left,right,INF)ifleft<right:mid=(left+right)/2node.left_child=self.make_tree(left,mid)node.right_child=self.make_tree(mid+1,right)returnnodedef_update(self,left,right,val,node):ifright<node.leftorleft>node.right:returnifnode.left_childandleft<=node.left_child.right:self._update(left,right,val,node.left_child)ifnode.right_childandright>=node.right_child.left:self._update(left,right,val,node.right_child)ifnode.left>=leftandnode.right<=right:node.data=min(node.data,val)defupdate(self,left,right,val):self._update(left,right,val,self.root)def_query(self,left,right,node):ifnodeisNoneorright<node.leftorleft>node.right:returnINFifnode.left>=leftandnode.right<=right:returnnode.datareturnmin(self._query(left,right,node.left_child),self._query(left,right,node.right_child))defquery(self,left,right):returnself._query(left,right,self.root)defdijkstra(N,S,edges):d=[INFforiinrange(N)]d[S]=0h=[]heappush(h,(0,S))foriinrange(N-1):min_dist,k=0,0ifnoth:breakwhileh:min_dist,k=heappop(h)ifmin_dist==d[k]:breakforj,winedges[k]:ifd[j]>d[k]+w:d[j]=d[k]+wheappush(h,(d[j],j))returnddeftarjan(N,S,T,edges):cnt=0bridges=[]visit=[0foriinrange(N)]low=[N+1foriinrange(N)]ret=[Falseforiinrange(N)]q=[0foriinrange(N+1)]q[0]=(S,-1,-1)top=0whiletop>=0:i,father,v=q[top]ifv==-1:ret[i]=(i==T)cnt=cnt+1visit[i]=low[i]=cntelifv<len(edges[i]):j,w,flag=edges[i][v]ifflag:ifj==q[top+1][0]:ret[i]=ret[i]orret[j]ifret[i]:low[i]=min(low[i],low[j])v+=1q[top]=(i,father,v)ifv<len(edges[i]):j,w,flag=edges[i][v]ifflag:ifnotvisit[j]:top+=1q[top]=(j,i,-1)else:ifj!=fatherandvisit[j]:low[i]=min(low[i],visit[j])else:iflow[i]==visit[i]andret[i]:iffather>=0:bridges.append((father,i))top-=1returnbridgesdefwork(N,S,T,edge_list,ds,dt,OPT,query):ifOPT>=INF:foru,vinquery:print"Infinity"returnedges=[[]foriinrange(N)]foru,v,winedge_list:ifds[u]+w==ds[v]:edges[u].append((v,w,True))edges[v].append((u,w,False))bridges=tarjan(N,S,T,edges)p=[0foriinrange(N)]defbfs(i,part):q=[i,]head=0whilehead<len(q):i=q[head]p[i]=partforj,w,flaginedges[i]:ifflagandp[j]==0:q.append(j)head+=1part=len(bridges)+1bridge_set={}foru,vinbridges:bridge_set[(u,v)]=(u,v)bridge_set[(v,u)]=(u,v)bfs(v,part)part-=1bfs(S,part)n=len(bridges)+1tree=SegTree(1,n)foru,v,winedge_list:ifp[u]andp[v]andp[u]<p[v]andbridge_set.get((u,v),None)isNone:tree.update(p[u],p[v]-1,ds[u]+w+dt[v])defanswer(u,v):b=bridge_set.get((u,v),None)ifbisNone:returnOPTelse:returntree.query(p[b[0]],p[b[1]]-1)foru,vinquery:result=answer(u,v)ifresult<INF:printresultelse:print"Infinity"defmain():N,M=map(int,raw_input().split())edges=[[]foriinrange(N)]edge_list=[]foriinrange(M):u,v,w=map(int,raw_input().split())edge_list.append((u,v,w))edge_list.append((v,u,w))edges[u].append((v,w))edges[v].append((u,w))S,T=map(int,raw_input().split())ds=dijkstra(N,S,edges)dt=dijkstra(N,T,edges)OPT=ds[T]query=[]Q=int(raw_input())foriinrange(Q):u,v=map(int,raw_input().split())query.append((u,v))work(N,S,T,edge_list,ds,dt,OPT,query)main()
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Going to the Office
You are viewing a single comment's thread. Return to all comments →
Python2 solution