Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
scipy dijkstra solution in 3rd party category for Power Supply by ciel
from collections import defaultdict
from scipy.sparse import *
def power_supply(a,p):
i=-1
m={}
q={}
b=[]
c=[]
for e in a:
if e[0] not in m:i+=1;m[e[0]]=i;q[i]=e[0]
if e[1] not in m:i+=1;m[e[1]]=i;q[i]=e[1]
b.append((m[e[0]],m[e[1]]))
c.append(1)
r=[1]*len(m)
mat=csr_matrix((c,zip(*b)),[len(m)]*2)
for k,v in p.items():
for i,e in enumerate(csgraph.dijkstra(mat,0,m[k])):
if e<=v:r[i]=0
return [q[i] for i,e in enumerate(r) if e]
Dec. 6, 2016
Comments:
