Problem p03450 (python)

Fixed submission:
# coding: UTF-8
from collections import deque
N,M = map(int,input().split())
link = [ [] for _ in range(N+1)]
value = [ -1 for _ in range(N+1)]

for _ in range(M):
  L,R,D = map(int,input().split())
  link[L].append((R,D))
  link[R].append((L,-D))

searched = set()
queue = deque()
for u in range(N+1):
  if u not in searched:
    queue.append(u)
    searched.add(u)
    value[u] = 0
    while queue:
      v = queue.popleft()
      for w,d in link[v]:
        if w not in searched:
          value[w] = value[v] + d
          queue.append(w)
          searched.add(w)

#verification
for v in range(N+1):
  for w,d in link[v]:
    if value[w] != value[v] + d:
      print("No")
      exit()
print("Yes")

Buggy submission (verdict: Runtime Error):
# coding: UTF-8
from collections import deque
#testdata

class Graph():
  #nodes
  #links
  def __init__(self):
    self.nodes = set()
    self.links = {}
    #nodes -> [tuple(f,cost)]
  
  def readtext(self):
    N,M = map(int,input().split())
    for i in range(M):
      v,w,c = map(int,input().split())
      self.addlink((v,w,c))
    
  
  def addlink(self,link):
    v,w,c = link
    if v not in self.nodes:
      self.nodes.add(v)
      self.links[v] = []
    if w not in self.nodes:
      self.nodes.add(w)
      self.links[w] = []
    
    if v in self.links:
      self.links[v].append((w,c))
      self.links[w].append((v,-c))
    else:
      self.links[v]=[]
      self.links[v].append((w,c))
      self.links[w].append((v,-c))
      
  def addlinks(self,links):
    for link in links:
      self.addlink(link)
  
  def depthfirstsearch(self,so):
    visited = set()
    linq = {}
    #O(links)
    for key in self.links:
      linq[key] = deque(self.links[key])
    #recursive subfunction
    def dfsrec(v,so):
      so.enter()
      visited.add(v)
      while linq[v]:
        cand,cost = linq[v].popleft()
        if cand not in visited:
          so.beforeEnter(v,cand,cost)
          so = dfsrec(cand,so)
      so.exit()
      return so
    
    #call subfunction
    noq = deque(self.nodes)
    while noq:
      x = noq.pop()
      if x not in visited:
        so.enterConnectedPart(x)
        so = dfsrec(x,so)
    return so

class Searcher():
  def __init__(self):
    pass
  def enter(self):
    pass
  def exit(self):
    pass
  def enterConnectedPart(self):
    pass
    
class TimeSearcher(Searcher):
  def __init__(self,graph):
    self.time = 0
    self.parts = 0
    
    self.dist = {} #nodes -> integer
    for node in graph.nodes:
      self.dist[node] = None
  
  def beforeEnter(self,v,cand,cost):
    self.dist[cand] = self.dist[v] + cost
  
  def enter(self):
    self.time += 1
  #def exit(self):
  #  self.time += 1
    
  def enterConnectedPart(self,start):
    self.parts += 1
    self.dist[start] = 0
  def show(self):
    for node in self.dist:
      print(str(node) + " at " + str(self.dist[node]))
  def validate(self,graph):
    for v in graph.links:
      for w,cost in graph.links[v]:
        if self.dist[w] != self.dist[v] + cost:
          return False
    return True

if __name__ == '__main__':
  g = Graph()
  g.readtext()
  so = TimeSearcher(g)
  so = g.depthfirstsearch(so)
  if so.validate(g):
    print("Yes")
  else:
    print("No")

Buggy submission (verdict: Runtime Error):
# coding: UTF-8
from collections import deque
N, M = map(int,input().split())
p = {}
link = set()
q = {}

for u in range(1,N+1):
  q[u] = deque()

for j in range(M):
  L,R,D = map(int,input().split())
  link.add((L,R,D))
  q[L].append((R,D))
  q[R].append((L,-D))
  
def depthfirstsearch(start):
  while q[start]:
    target,d = q[start].pop()
    if target not in p:
      p[target] = p[start] + d
      depthfirstsearch(target)

for s in range(1,N+1):
  if s not in p:
    p[s] = 0
    depthfirstsearch(s)

yes = True
for L,R,D in link:
  if p[R] != p[L] + D:
    print("No")
    yes = False
if yes:
  print("Yes")

Buggy submission (verdict: Runtime Error):
# coding: UTF-8
from collections import deque
N, M = map(int,input().split())
p = {}
link = set()
q = {}

for u in range(1,N+1):
  q[u] = deque()

for j in range(M):
  L,R,D = map(int,input().split())
  link.add((L,R,D))
  q[L].append((R,D))
  q[R].append((L,-D))
  
def depthfirstsearch(start):
  while q[start]:
    target,d = q[start].pop()
    if target not in p:
      p[target] = p[start] + d
      depthfirstsearch(target)

for start in range(1,N+1):
  if start not in p:
    p[start] = 0
    depthfirstsearch(start)

for L,R,D in link:
  if p[R] != p[L] + D:
    print("No")
    yes = False
if yes:
  print("Yes")

Buggy submission (verdict: Runtime Error):
# coding: UTF-8
from collections import deque
N, M = map(int,input().split())
p = {}
link = set()
q = {}

for u in range(1,N+1):
  q[u] = deque()

for j in range(M):
  L,R,D = map(int,input().split())
  link.add((L,R,D))
  #link.add((R,L,-D))
  q[L].append((R,D))
  q[R].append((L,-D))
  
def depthfirstsearch(start):
  while q[start]:
    target,d = q[start].pop()
    if target not in p:
      p[target] = p[start] + d
      depthfirstsearch(target)



for start in range(1,N+1):
  if start not in p:
    p[start] = 0
    depthfirstsearch(start)

#for u in range(1,N+1):
  #print("position of " + str(u) + " = " + str(p[u]))

for L,R,D in link:
  if p[R] != p[L] + D:
    #print((L,R))
    #print((p[L],D,p[R]))
    print("No")
    exit()

print("Yes")

Buggy submission (verdict: Runtime Error):
# coding: UTF-8
from collections import deque
visited = set()
d = {}
arrow = {}
nodes = deque()

raw = input().split()
N = int(raw[0])
M = int(raw[1])

for i in range(1,N+1):
  arrow[i] = deque()
  d[i] = 0
  nodes.append(i)

for i in range(M):
  raw = list(map(int,input().split()))
  L = raw[0]
  R = raw[1]
  D = raw[2]
  arrow[L].append((R,D))
  arrow[R].append((L,-D))

def dfsl(v):
  #矛盾が見つかればFalseを返す
  visited.add(v)
  while arrow[v]:
    w,cost = arrow[v].pop()
    
    if w not in visited:
      d[w] = d[v] + cost
      return dfsl(w)
    else:
      if d[w] != d[v] + cost:
        return False
  return True

ans = True
while nodes:
  u = nodes.pop()
  if u not in visited:
    d[u] = 0
    ans = dfsl(u)
    if not ans:
      break

for v in range(1,N+1):
  while arrow[v] and not ans:
    w,c = arrow[v].pop()
    if d[w] != d[v] + c:
      ans = False
      break
  

if ans:
  print("Yes")
else:
  print("No")

Buggy submission (verdict: Runtime Error):
# coding: UTF-8
from collections import deque
visited = set()
d = {}
arrow = {}
nodes = deque()

raw = input().split()
N = int(raw[0])
M = int(raw[1])

for i in range(1,N+1):
  arrow[i] = deque()
  d[i] = 0
  nodes.append(i)

for i in range(M):
  raw = list(map(int,input().split()))
  L = raw[0]
  R = raw[1]
  D = raw[2]
  arrow[L].append((R,D))
  arrow[R].append((L,-D))

def dfsl(v):
  #矛盾が見つかればFalseを返す
  visited.add(v)
  while arrow[v]:
    w,cost = arrow[v].pop()
    
    if w not in visited:
      d[w] = d[v] + cost
      return dfsl(w)
    else:
      if d[w] != d[v] + cost:
        return False
  return True

ans = True
while nodes:
  u = nodes.pop()
  if u not in visited:
    d[u] = 0
    ans = dfsl(u)
    if not ans:
      break

if ans:
  print("Yes")
else:
  print("No")

Buggy submission (verdict: Runtime Error):
# coding: UTF-8
from collections import deque
visited = set()
d = {}
arrow = {}
raw = input().split()
N = int(raw[0])
M = int(raw[1])

for i in range(1,N+1):
  arrow[i] = deque()
  d[i] = 0

for i in range(M):
  raw = list(map(int,input().split()))
  L = raw[0]
  R = raw[1]
  D = raw[2]
  arrow[L].append((R,D))
  arrow[R].append((L,-D))

def dfsl(v):
  #矛盾が見つかればFalseを返す
  visited.add(v)
  while arrow[v]:
    w,cost = arrow[v].pop()
    
    if w not in visited:
      d[w] = d[v] + cost
      #print("not visited")
      #print([d[v],d[w],cost])
      return dfsl(w)
    else:
      if d[w] != d[v] + cost:
        #print("visited")
        #print([d[v],d[w],cost])
        return False
  return True

ans = True
for u in range(1,N+1):
  if u not in visited:
    d[u] = 0
    ans = dfsl(u)
    if not ans:
      break
  

if ans:
  print("Yes")
else:
  print("No")

Buggy submission (verdict: Runtime Error):
# coding: UTF-8
from collections import deque
visited = set()
d = {}
arrow = {}
raw = input().split()
N = int(raw[0])
M = int(raw[1])

for i in range(1,N+1):
  arrow[i] = deque()
  d[i] = None

for i in range(M):
  raw = list(map(int,input().split()))
  L = raw[0]
  R = raw[1]
  D = raw[2]
  arrow[L].append((R,D))
  arrow[R].append((L,-D))

def dfsl(v):
  #矛盾が見つかればFalseを返す
  visited.add(v)
  while arrow[v]:
    w,cost = arrow[v].pop()
    
    if w not in visited:
      d[w] = d[v] + cost
      #print("not visited")
      #print([d[v],d[w],cost])
      return dfsl(w)
    else:
      if d[w] != d[v] + cost:
        #print("visited")
        #print([d[v],d[w],cost])
        return False
  return True

ans = True
for u in range(1,N+1):
  if u not in visited:
    d[u] = 0
    ans = dfsl(u)
    if not ans:
      break
    else:
      continue

if ans:
  print("Yes")
else:
  print("No")