Problem p04003 (python)

Fixed submission:
from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  if x not in d:
    return -1
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))

Buggy submission (verdict: Runtime Error):
from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))

Buggy submission (verdict: Runtime Error):
from collections import defaultdict,deque
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))

Buggy submission (verdict: Runtime Error):
from collections import defaultdict,deque
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+c<<30].add(b+c<<30)
  G[b+c<<30].add(a+c<<30)
  G[a].add(a+c<<30)
  G[b].add(b+c<<30)
  G[a+c<<30].add(a)
  G[b+c<<30].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**7:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**7:
            stack.append((i,m+1))
  return -1

print(BFS(1))

Buggy submission (verdict: Runtime Error):
from collections import defaultdict,deque
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[(a-1,c-1)].add((b-1,c-1))
  G[(b-1,c-1)].add((a-1,c-1))
  G[(a-1,-1)].add((a-1,c-1))
  G[(b-1,-1)].add((b-1,c-1))
  G[(a-1,c-1)].add((a-1,-1))
  G[(b-1,c-1)].add((b-1,-1))
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  d[x]=0
  stack=deque([(x,-1,0)])
  while stack:
    a,c,m=stack.popleft()
    if a==N-1 and c==-1:
      return m
    if d[(a,c)]>m:
      d[(a,c)]=m
      if c>=0:
        for i in G[(a,c)]:
          if d[i]>10**30:
            stack.appendleft((i[0],i[1],m))
      else: 
        for i in G[(a,c)]:
          if d[i]>10**30:
            stack.append((i[0],i[1],m+1))
  return -1

print(BFS(0))

Buggy submission (verdict: Runtime Error):
from collections import defaultdict,deque
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[(a-1,c-1)].add((b-1,c-1))
  G[(b-1,c-1)].add((a-1,c-1))
  G[(a-1,-1)].add((a-1,c-1))
  G[(b-1,-1)].add((b-1,c-1))
  G[(a-1,c-1)].add((a-1,-1))
  G[(b-1,c-1)].add((b-1,-1))
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  d[x]=0
  stack=deque([(x,-1,0)])
  while stack:
    a,c,m=stack.popleft()
    if a==N-1 and c==-1:
      return m
    d[(a,c)]=min(d[(a,c)],m)
    if c>=0:
      for i in G[(a,c)]:
        if d[i]>10**30:
          stack.appendleft((i[0],i[1],m))
    else: 
      for i in G[(a,c)]:
        if d[i]>10**30:
          stack.append((i[0],i[1],m+1))
  return -1

print(BFS(0))