Problem p04003 (python)

Fixed submission:
from collections import deque
N, M = map(int, input().split())
F_C_of_S = [{} for i in range(N)]
#Companies of Station
C_of_S = {}

#def Union-find
parent = [-1]*M
def root(x):
	if (parent[x] < 0): return x
	else:
		parent[x] = y = root(parent[x])
		return y

def unite(x, y):
	px = root(x)
	py = root(y)
	if (px == py): return False
	if (parent[px] > parent[py]):
		px = root(y)
		py = root(x)
	parent[px] += parent[py]
	parent[py] = px
	return True


#Union-find
pqcs = []
for i in range(M):
	p, q, c = map(int, input().split())
	p -= 1; q -= 1;
	pqcs += [(p, q, c)]
	
	#The first
	if not c in F_C_of_S[p]: F_C_of_S[p][c] = i
	#else
	else: unite(F_C_of_S[p][c], i)
	C_of_S.setdefault(p, set()).add(c)
	
	#The first
	if not (c in F_C_of_S[q]):F_C_of_S[q][c] = i
	#else
	else: unite(F_C_of_S[q][c], i)
	C_of_S.setdefault(q, set()).add(c)

#stations of company
S_of_C = {}
for i in range(M):
	p, q, c = pqcs[i]
	c_set = S_of_C.setdefault(root(i), set())
	c_set.add(p)
	c_set.add(q)


Q = deque([(0, 0, 0)])
#cost to go to the stations from station_0
dist = [float('inf')]*N
dist[0] = 0

gdist = [float('inf')]*M

while Q:
	cost, v, flag = Q.popleft()
	
	if not (flag):#(flag == 0) then gdist_update
		if (dist[v] < cost) or (v not in C_of_S):
			continue
		for l in F_C_of_S[v].values():
			l = root(l)
			if (cost < gdist[l]):
				gdist[l] = cost
				Q.appendleft((cost, l, 1))
	
	else:#(flag == 1) then dist_update
		if (gdist[v] < cost) or (v not in S_of_C):
			continue
		for s in S_of_C[v]:
			if (cost+1 < dist[s]):
				dist[s] = cost+1
				Q.append((cost+1, s, 0))

print(dist[N - 1] if dist[N - 1] < float('inf') else -1)

Buggy submission (verdict: Runtime Error):
from collections import deque

N, M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
F_C_of_S = [{} for i in range(N)]
# Companies of Station
C_of_S = {}

# def Union-find
parent = {i:i for i in range(M)}
def root(x):
    if x == parent[x]:
        return x
    parent[x] = y = root(parent[x])
    return y
def unite(x, y):
    px = root(x); py = root(y);
    if px < py:
        parent[py] = px
    else:
        parent[px] = py


# Union-find
pqcs = []
#stations of company
S_of_C = {}
for i in range(M):
    p, q, c = map(int, input().split())
    p -= 1; q -= 1;
    pqcs += [(p, q, c)]

    if not 10**6+c in parent:
        parent[10**6+c] = i
    else:
        unite(10**6+c, i)

    C_of_S.setdefault(p, set()).add(root(i))
    C_of_S.setdefault(q, set()).add(root(i))
    c_set = S_of_C.setdefault(root(i), set())
    c_set.add(p)
    c_set.add(q)


Q = deque([(0, 0, 0)])
# cost to go to the station from station_0
dist = [float('inf')] * N
dist[0] = 0
# cost to get on the line
line_dist = [float('inf')] * M

while Q:
    cost, v, flag = Q.popleft()
    if not (flag):  # (flag == 0) then line_dist_update
        # v is station
        for l in C_of_S[v]:
            if (cost < line_dist[l]):
                line_dist[l] = cost
                Q.appendleft((cost, l, 1))
    else:  # (flag == 1) then dist_update
        # v is company
        for s in S_of_C[v]:
            if (cost + 1 < dist[s]):
                dist[s] = cost + 1
                Q.append((cost + 1, s, 0))

print(dist[N - 1] if dist[N - 1] < float('inf') else -1)

Buggy submission (verdict: Runtime Error):
from collections import deque
N, M = map(int, input().split())
F_C_of_S = [{} for i in range(N)]
#Companies of Station
C_of_S = {}

#def Union-find
parent = [-1]*M
def root(x):
	if (parent[x] < 0): return x
	else:
		parent[x] = y = root(parent[x])
		return y

def unite(x, y):
	px = root(x)
	py = root(y)
	if (px == py): return False
	"""
	if (parent[px] > parent[py]):
		px = root(y)
		py = root(x)
	parent[px] += parent[py]
	parent[py] = px
	"""
	parent[py] += parent[px]
	parent[px] = px
	return True


#Union-find
pqcs = []
#stations of company
S_of_C = {}
for i in range(M):
	p, q, c = map(int, input().split())
	p -= 1; q -= 1;
	pqcs += [(p, q, c)]
	
	#The first
	if not c in F_C_of_S[p]:
		#Numbering in order of appearance
		F_C_of_S[p][c] = i
	#else
	else:
		unite(F_C_of_S[p][c], i)
	#set a line that can ride from the station
	C_of_S.setdefault(p, set()).add(c)
	
	if not (c in F_C_of_S[q]):
		F_C_of_S[q][c] = i
	else:
		unite(F_C_of_S[q][c], i)
	C_of_S.setdefault(q, set()).add(c)
	
	c_set = S_of_C.setdefault(root(i), set())
	c_set.add(p)
	c_set.add(q)

#stations of company
#S_of_C = {}
#for i in range(M):
	#p, q, c = pqcs[i]
	#c_set = S_of_C.setdefault(root(i), set())
	#c_set.add(p)
	#c_set.add(q)


Q = deque([(0, 0, 0)])
#cost to go to the station from station_0
dist = [float('inf')]*N
dist[0] = 0
#cost to get on the line 
gdist = [float('inf')]*M

while Q:
	cost, v, flag = Q.popleft()
	if not (flag):#(flag == 0) then gdist_update
		#v is station
		for l in F_C_of_S[v].values():
			l = root(l)
			if (cost < gdist[l]):
				gdist[l] = cost
				Q.appendleft((cost, l, 1))
	else:#(flag == 1) then dist_update
		#v is company
		for s in S_of_C[v]:
			if (cost+1 < dist[s]):
				dist[s] = cost+1
				Q.append((cost+1, s, 0))

print(dist[N - 1] if dist[N - 1] < float('inf') else -1)

Buggy submission (verdict: Runtime Error):
from collections import deque
N, M = map(int, input().split())
F_C_of_S = [{} for i in range(N)]
#Companies of Station
C_of_S = {}

#def Union-find
parent = [-1]*M
def root(x):
	if (parent[x] < 0): return x
	else:
		parent[x] = y = root(parent[x])
		return y

def unite(x, y):
	px = root(x)
	py = root(y)
	if (px == py): return False
	if (parent[px] > parent[py]):
		px = root(y)
		py = root(x)
	parent[px] += parent[py]
	parent[py] = px
	return True


#Union-find
pqcs = []
for i in range(M):
	p, q, c = map(int, input().split())
	p -= 1; q -= 1;
	pqcs += [(p, q, c)]
	
	#The first
	if not c in F_C_of_S[p]:
		#Numbering in order of appearance
		F_C_of_S[p][c] = i
	#else
	else:
		unite(F_C_of_S[p][c], i)
	#set a line that can ride from the station
	C_of_S.setdefault(p, set()).add(c)
	
	if not (c in F_C_of_S[q]):
		F_C_of_S[q][c] = i
	else:
		unite(F_C_of_S[q][c], i)
	C_of_S.setdefault(q, set()).add(c)
	
	#stations of company
	S_of_C = {}
	c_set = S_of_C.setdefault(root(i), set())
	c_set.add(p)
	c_set.add(q)
	
"""
#stations of company
S_of_C = {}
for i in range(M):
	p, q, c = pqcs[i]
	c_set = S_of_C.setdefault(root(i), set())
	c_set.add(p)
	c_set.add(q)
"""

Q = deque([(0, 0, 0)])
#cost to go to the station from station_0
dist = [float('inf')]*N
dist[0] = 0
#cost to get on the line 
gdist = [float('inf')]*M

while Q:
	cost, v, flag = Q.popleft()
	if not (flag):#(flag == 0) then gdist_update
		#v is station
		for l in F_C_of_S[v].values():
			l = root(l)
			if (cost < gdist[l]):
				gdist[l] = cost
				Q.appendleft((cost, l, 1))
	else:#(flag == 1) then dist_update
		#v is company
		for s in S_of_C[v]:
			if (cost+1 < dist[s]):
				dist[s] = cost+1
				Q.append((cost+1, s, 0))

print(dist[N - 1] if dist[N - 1] < float('inf') else -1)

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush
N,M = map(int, input().split())
edges = [[] for _ in range(N)]
cs = set{}
for i in range(M):
	p,q,c = map(int, input().split())
	cs += c
	edges[p-1] += [[q-1, c]]
	edges[q-1] += [[p-1, c]]
c_num = len(cs)
distance = [[float('inf')]*(c_num+1) for _ in range(N)]
distance[0][0] = 0
min_distance = [float('inf')]*N
min_distance[0] = 0
Q = [[0, 0]]

while Q:
	s_now,c_now = heappop(Q)
	for t, c in edges[s_now]:
		if min_distance[t] > distance[s_now][c_now] + (c_now != c):
			distance[t][c] = distance[s_now][c_now] + (c_now != c)
			min_distance[t] = distance[t][c]
			heappush(Q, [t, c])
print(min_distance[N-1] if min_distance[N-1] != float('inf') else -1)

Buggy submission (verdict: Runtime Error):
from collections import deque
N,M = map(int, input().split())
edges = [[] for _ in range(N)]
c_max = 0
for i in range(M):
	p,q,c = map(int, input().split())
	c_max = max(c, c_max)
	edges[p-1] += [[q-1, c]]
	edges[q-1] += [[p-1, c]]
distance = [[float('inf')]*(c_max+1) for _ in range(N)]
distance[0][0] = 0
min_distance = [float('inf')]*N
min_distance[0] = 0
Q = deque([[0,0]])


flag = False
while Q:
	s_now,c_now = Q.popleft()
	for t, c in edges[s_now]:
		if min_distance[t] > distance[s_now][c_now] + (c_now != c):
			distance[t][c] = distance[s_now][c_now] + (c_now != c)
			min_distance[t] = distance[t][c]
			if c_now == c:
				Q.appendleft([t, c])
				continue
			Q.append([t, c])
print(min_distance[N-1] if min_distance[N-1] != float('inf') else -1)

Buggy submission (verdict: Runtime Error):
from collections import deque
N,M = map(int, input().split())
edges = [[] for _ in range(N)]
c_max = 0
for i in range(M):
	p,q,c = map(int, input().split())
	c_max = max(c, c_max)
	edges[p-1] += [[q-1, c]]
	edges[q-1] += [[p-1, c]]
distance = [[float('inf')]*(c_max+1) for _ in range(N)]
distance[0][0] = 0
Q = deque([[0,0]])


flag = False
while Q:
	s_now,c_now = Q.popleft()
	for t, c in edges[s_now]:
		t_dist = min(distance[t])
		if t_dist > distance[s_now][c_now] + (c_now != c):
			distance[t][c] = distance[s_now][c_now] + (c_now != c)
			if c_now == c:
				Q.appendleft([t, c])
				continue
			Q.append([t, c])
d = min(distance[N-1])
print(d if d != float('inf') else -1)

Buggy submission (verdict: Runtime Error):
from collections import deque
N,M = map(int, input().split())
edges = [[] for _ in range(N)]
c_max = 0
for i in range(M):
	p,q,c = map(int, input().split())
	c_max = max(c, c_max)
	edges[p-1] += [[q-1, c]]
	edges[q-1] += [[p-1, c]]
distance = [[float('inf')]*(c+1) for _ in range(N)]
distance[0][0] = 0
Q = deque([[0,0]])


flag = False
while Q:
	s_now,c_now = Q.popleft()
	for t, c in edges[s_now]:
		t_dist = min(distance[t])
		if t_dist > distance[s_now][c_now] + (c_now != c):
			distance[t][c] = distance[s_now][c_now] + (c_now != c)
			if c_now == c:
				Q.appendleft([t, c])
				continue
			Q.append([t, c])
d = min(distance[N-1])
print(d if d != float('inf') else -1)

Buggy submission (verdict: Runtime Error):
from collections import deque
N,M = map(int, input().split())
if M == 0:
	print(-1)
	exit()
Q = {0:deque([1])}
distance = {1:0}

#辺へ重み付け
edges = {}
for _ in range(M):
	p,q,c = map(int, input().split())
	edge = {}
	edge[c*10**6+q] = 0
	edge[p] = 0
	edges.setdefault(c*10**6+p, {})
	edges[c*10**6+p].update(edge)
	edge = {}
	edge[c*10**6+p] = 0
	edge[q] = 0
	edges.setdefault(c*10**6+q, {})
	edges[c*10**6+q].update(edge)
	edge = {}
	edge[c*10**6+p] = 1
	edges.setdefault(p, {})
	edges[p].update(edge)
	edge = {}
	edge[c*10**6+q] = 1
	edges.setdefault(q, {})
	edges[q].update(edge)

flag = False
while 1:
	for i in range(len(Q)):                            
		if not (Q[i]):
			continue
		flag = True
		target_min_ind = Q[i].popleft()
		target_node = edges[target_min_ind]
		break
	if not (flag):
		break

	for key, value in target_node.items():
		distance.setdefault(key, float('inf'))
		dist = distance[target_min_ind] + value
		if distance[key] > dist:
			distance[key] = dist
			Q.setdefault(dist, deque())
			Q[dist].append(key)
		if key == N:
			flag = False
	if not (flag):
		break

print(distance[N] if distance[N] != float('inf') else -1)

Buggy submission (verdict: Runtime Error):
from collections import deque
N,M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
Q = {0:deque([1])}
distance = {1:0}

#辺へ重み付け
edges = {}
for p,q,c in (list(map(int, input().split())) for _ in range(M)):
	edge = {}
	edge[c*10**6+q] = 0
	edge[p] = 0
	edges.setdefault(c*10**6+p, {})
	edges[c*10**6+p].update(edge)
	edge = {}
	edge[c*10**6+p] = 0
	edge[q] = 0
	edges.setdefault(c*10**6+q, {})
	edges[c*10**6+q].update(edge)
	edge = {}
	edge[c*10**6+p] = 1
	edges.setdefault(p, {})
	edges[p].update(edge)
	edge = {}
	edge[c*10**6+q] = 1
	edges.setdefault(q, {})
	edges[q].update(edge)

flag = False
while 1:
	for i in range(len(Q)):                            
		if not (Q[i]):
			continue
		flag = True
		target_min_ind = Q[i].popleft()
		target_node = edges[target_min_ind]
		break
	if not (flag):
		break

	for key, value in target_node.items():
		distance.setdefault(key, float('inf'))
		dist = distance[target_min_ind] + value
		if distance[key] > dist:
			distance[key] = dist
			Q.setdefault(dist, deque())
			Q[dist].append(key)
		if key == N:
			flag = False
	if not (flag):
		break

print(distance[N] if distance[N] != float('inf') else -1)

Buggy submission (verdict: Runtime Error):
N,M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
pqcs = [list(map(int, input().split())) for _ in range(M)]
c_max = max(list(map(lambda x: x[2],pqcs)))
node_num = (c_max+1)*N
unsearached_nodes = list(range(node_num))#0～N-1(n-1)が乗換経由ノード/路線iの駅nは3*i+(n-1)番ノード
#opt_nodes = [-1]*node_num
distance = [float('inf')]*node_num
distance[0] = 0
cost = 0
edges = [[float('inf')]*node_num for _ in range(node_num)]
#辺へ重み付け
for p,q,c in pqcs:
    edges[3*c+(p-1)][3*c+(q-1)] = 0
    edges[3*c+(q-1)][3*c+(p-1)] = 0
    edges[p-1][3*c+(p-1)] = 1
    edges[q-1][3*c+(q-1)] = 1
    edges[3*c+(p-1)][p-1] = 0
    edges[3*c+(q-1)][q-1] = 0

while (distance[N-1] == float('inf')):
    temp_min_dist = float('inf')
    for unsearched_ind in unsearached_nodes:
        if temp_min_dist > distance[unsearched_ind]:
            temp_min_dist = distance[unsearched_ind]
            target_min_ind = unsearched_ind
    if temp_min_dist == float('inf'):
        break
    unsearached_nodes.remove(target_min_ind)
    target_node = edges[target_min_ind]
    flag = False
    for index, rota_dist in enumerate(target_node):
        if rota_dist != float('inf'):
            if distance[index] > distance[target_min_ind] + rota_dist:
                distance[index] = distance[target_min_ind] + rota_dist
                #opt_nodes[index] = target_min_ind

print(distance[N-1] if distance[N-1] != float('inf') else -1)

Buggy submission (verdict: Runtime Error):
N,M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
pqcs = [list(map(int, input().split())) for _ in range(M)]
c_max = max(list(map(lambda x: x[2],pqcs)))
node_num = (c_max+1)*N
unsearached_nodes = list(range(node_num))#0～N-1(n-1)が乗換経由ノード/路線iの駅nは3*i+(n-1)番ノード
#opt_nodes = [-1]*node_num
distance = [float('inf')]*node_num
distance[0] = 0
cost = 0
edges = [[float('inf')]*node_num for _ in range(node_num)]
#辺へ重み付け
for p,q,c in pqcs:
    edges[3*c+(p-1)][3*c+(q-1)] = 0
    edges[3*c+(q-1)][3*c+(p-1)] = 0
    edges[p-1][3*c+(p-1)] = 1
    edges[q-1][3*c+(q-1)] = 1
    edges[3*c+(p-1)][p-1] = 0
    edges[3*c+(q-1)][q-1] = 0

while (distance[N-1] == float('inf')):
    temp_min_dist = float('inf')
    for unsearched_ind in unsearached_nodes:
        if temp_min_dist > distance[unsearched_ind]:
            temp_min_dist = distance[unsearched_ind]
            target_min_ind = unsearched_ind
    unsearached_nodes.remove(target_min_ind)
    target_node = edges[target_min_ind]
    flag = False
    for index, rota_dist in enumerate(target_node):
        if rota_dist != float('inf'):
            if distance[index] > distance[target_min_ind] + rota_dist:
                distance[index] = distance[target_min_ind] + rota_dist
                #opt_nodes[index] = target_min_ind

print(distance[N-1] if distance[N-1] != float('inf') else -1)

Buggy submission (verdict: Runtime Error):
N,M = map(int, input().split())
"""
if M == 0:
    print(-1)
    exit()
"""
pqcs = [list(map(int, input().split())) for _ in range(M)]
c_max = max(list(map(lambda x: x[2],pqcs)))
node_num = (c_max+1)*N
unsearached_nodes = list(range(node_num))#0～N-1(n-1)が乗換経由ノード/路線iの駅nは3*i+(n-1)番ノード
#opt_nodes = [-1]*node_num
distance = [float('inf')]*node_num
distance[0] = 0
cost = 0
edges = [[float('inf')]*node_num for _ in range(node_num)]
#辺へ重み付け
for p,q,c in pqcs:
    edges[3*c+(p-1)][3*c+(q-1)] = 0
    edges[3*c+(q-1)][3*c+(p-1)] = 0
    edges[p-1][3*c+(p-1)] = 1
    edges[q-1][3*c+(q-1)] = 1
    edges[3*c+(p-1)][p-1] = 0
    edges[3*c+(q-1)][q-1] = 0

while (distance[N-1] == float('inf')):
    temp_min_dist = float('inf')
    for unsearched_ind in unsearached_nodes:
        if temp_min_dist > distance[unsearched_ind]:
            temp_min_dist = distance[unsearched_ind]
            target_min_ind = unsearched_ind
    unsearached_nodes.remove(target_min_ind)
    target_node = edges[target_min_ind]
    flag = False
    for index, rota_dist in enumerate(target_node):
        if rota_dist != float('inf'):
            if distance[index] > distance[target_min_ind] + rota_dist:
                distance[index] = distance[target_min_ind] + rota_dist
                #opt_nodes[index] = target_min_ind

print(distance[N-1] if distance[N-1] != float('inf') else -1)

Buggy submission (verdict: Runtime Error):
N,M = map(int, input().split())
"""
if M == 0:
    print(-1)
    exit()
"""
pqcs = [list(map(int, input().split())) for _ in range(M)]
c_max = max(list(map(lambda x: x[2],pqcs)))
node_num = (c_max+1)*N
unsearached_nodes = list(range(node_num))#0～N-1(n-1)が乗換経由ノード/路線iの駅nは3*i+(n-1)番ノード
#opt_nodes = [-1]*node_num
distance = [float('inf')]*node_num
distance[0] = 0
cost = 0
edges = [[float('inf')]*node_num for _ in range(node_num)]
#辺へ重み付け
for p,q,c in pqcs:
    edges[3*c+(p-1)][3*c+(q-1)] = 0
    edges[3*c+(q-1)][3*c+(p-1)] = 0
    edges[p-1][3*c+(p-1)] = 1
    edges[q-1][3*c+(q-1)] = 1
    edges[3*c+(p-1)][p-1] = 0
    edges[3*c+(q-1)][q-1] = 0

while (distance[N-1] == float('inf')):
    temp_min_dist = float('inf')
    for unsearched_ind in unsearached_nodes:
        if temp_min_dist > distance[unsearched_ind]:
            temp_min_dist = distance[unsearched_ind]
            target_min_ind = unsearched_ind
    unsearached_nodes.remove(target_min_ind)
    target_node = edges[target_min_ind]
    flag = False
    for index, rota_dist in enumerate(target_node):
        if rota_dist != float('inf'):
            if distance[index] > distance[target_min_ind] + rota_dist:
                distance[index] = distance[target_min_ind] + rota_dist
                #opt_nodes[index] = target_min_ind

print(distance[N-1] if distnce[N-1] != float('inf') else -1)

Buggy submission (verdict: Runtime Error):
N,M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
pqcs = [list(map(int, input().split())) for _ in range(M)]
c_max = max(list(map(lambda x: x[2],pqcs)))
node_num = (c_max+1)*N
unsearached_nodes = list(range(node_num))#0～N-1(n-1)が乗換経由ノード/路線iの駅nは3*i+(n-1)番ノード
#opt_nodes = [-1]*node_num
distance = [float('inf')]*node_num
distance[0] = 0
cost = 0
edges = [[float('inf')]*node_num for _ in range(node_num)]
#辺へ重み付け
for p,q,c in pqcs:
    edges[3*c+(p-1)][3*c+(q-1)] = 0
    edges[3*c+(q-1)][3*c+(p-1)] = 0
    edges[p-1][3*c+(p-1)] = 1
    edges[q-1][3*c+(q-1)] = 1
    edges[3*c+(p-1)][p-1] = 0
    edges[3*c+(q-1)][q-1] = 0

while (distance[N-1] == float('inf')):
    temp_min_dist = float('inf')
    for unsearched_ind in unsearached_nodes:
        if temp_min_dist > distance[unsearched_ind]:
            temp_min_dist = distance[unsearched_ind]
            target_min_ind = unsearched_ind
    unsearached_nodes.remove(target_min_ind)
    target_node = edges[target_min_ind]
    for index, rota_dist in enumerate(target_node):
        if rota_dist != float('inf'):
            if distance[index] > distance[target_min_ind] + rota_dist:
                distance[index] = distance[target_min_ind] + rota_dist
                #opt_nodes[index] = target_min_ind

print(distance[N-1])