class Graph(): def __init__(self,size,directed=False): self.dir=directed self.size=size self.gr=[[] for i in range(size)] self.edges=[] def add_edge(self,u,v,status={}): self.gr[u].append(self.Edge(u,v,status)) if not(self.dir): self.gr[v].append(self.Edge(v,u,status)) self.edges.append(self.Edge(u,v,status)) def node(self,v): return self.gr[v] def __getitem__(self,v): return self.gr[v] class Edge(): def __init__(self,st,to,status): self.st=st self.to=to self.status=status def __getitem__(self,val): return self.status[val] from math import inf from heapq import heappop,heappush def dijkstra(graph,start,weight): dist=[inf for i in range(graph.size)] used=[False for i in range(graph.size)] dist[start]=0 vert=[(0,start)] while len(vert)>0: dis,pos=heappop(vert) if used[pos]: continue used[pos]=True for i in graph.node(pos): if dis+weight(i)