Problem:


Score : 600 points

Problem Statement

Snuke's town has a subway system, consisting of N stations and M railway lines. The stations are numbered 1 through N. Each line is operated by a company. Each company has an identification number.

The i-th ( 1 \leq i \leq M ) line connects station p_i and q_i bidirectionally. There is no intermediate station. This line is operated by company c_i.

You can change trains at a station where multiple lines are available.

The fare system used in this subway system is a bit strange. When a passenger only uses lines that are operated by the same company, the fare is 1 yen (the currency of Japan). Whenever a passenger changes to a line that is operated by a different company from the current line, the passenger is charged an additional fare of 1 yen. In a case where a passenger who changed from some company A's line to another company's line changes to company A's line again, the additional fare is incurred again.

Snuke is now at station 1 and wants to travel to station N by subway. Find the minimum required fare.

Constraints

2 \leq N \leq 10^5

0 \leq M \leq 2×10^5

1 \leq p_i \leq N (1 \leq i \leq M)

1 \leq q_i \leq N (1 \leq i \leq M)

1 \leq c_i \leq 10^6 (1 \leq i \leq M)

p_i \neq q_i (1 \leq i \leq M)

Input

The input is given from Standard Input in the following format:

N M
p_1 q_1 c_1
:
p_M q_M c_M

Output

Print the minimum required fare. If it is impossible to get to station N by subway, print -1 instead.

Sample Input 1

3 3
1 2 1
2 3 1
3 1 2

Sample Output 1

1

Use company 1's lines: 1 → 2 → 3. The fare is 1 yen.

Sample Input 2

8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5

Sample Output 2

2

First, use company 1's lines: 1 → 3 → 2 → 5 → 6. Then, use company 5's lines: 6 → 7 → 8. The fare is 2 yen.

Sample Input 3

2 0

Sample Output 3

-1



Sample input:
3 3
1 2 1
2 3 1
3 1 2


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()

    return

#B
def B():
    n = I()

    return

#C
def C():
    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        v[a].append((b,c))
        v[b].append((a,c))
    d = defaultdict(lambda : float("inf"))
    d[(0,0)] = 0
    q = [(0,0,0)]
    while q:
        dx,x,cx = heappop(q)
        for y,c in v[x]:
            nd = dx+(cx != c)
            if nd < d[(y,c)]:
                d[(y,c)] = nd
                heappush(q,(nd,y,c))
    ans = float("inf")
    for i in range(1000001):
        if d[(n-1,i)] < ans:
            ans = d[(n-1,i)]
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)
    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(m):
    p, q, c = map(int, input().split())
    p, q, c = p-1, q-1, c-1
    edges[p].append((q, c))
    edges[q].append((p, c))

que = deque()
cost = [float("inf")]*n
colr = [-1]*n
# now, prev,prev_color, cost
que.append((0, -1, -1, 0))

while que:
    now, prev, prev_color, cost_now = que.popleft()
    if cost[now] < cost_now or (cost[now] == cost_now and colr[now] == prev_color):
        continue
    cost[now] = cost_now
    colr[now] = prev_color
    for to, color in edges[now]:
        if to == prev:
            continue
        if cost_now+int(color!=prev_color) <= cost[to]:
            que.append((to, now, color, cost_now+int(color!=prev_color)))
if cost[-1] == float("inf"):
    print(-1)
else:
    print(cost[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

L = 32
mask = (1 << L) - 1
N,M = map(int,input().split())
graph = defaultdict(list)
for _ in range(M):
    p,q,c = map(int,input().split())
    p <<= L
    q <<= L
    graph[p].append(p+c)
    graph[p+c].append(p)
    graph[q].append(q+c)
    graph[q+c].append(q)
    graph[p+c].append(q+c)
    graph[q+c].append(p+c)

INF = 10 ** 9
dist = defaultdict(lambda: INF)

start = 1 << L
goal = N << L

q = [start] # 0 が会社に属していない状態
dist[start] = 0
d = 0
while q:
    qq = []
    while q:
        x = q.pop()
        if x & mask == 0:
            for y in graph[x]:
                if dist[y] <= d + 1:
                    continue
                dist[y] = d + 1
                qq.append(y)
        else:
            for y in graph[x]:
                if dist[y] <= d:
                    continue
                dist[y] = d
                q.append(y)
    d += 1
    q = qq

answer = dist[goal]
if answer == INF:
    answer = -1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

N,M = map(int,input().split())
graph = defaultdict(list)
for _ in range(M):
    p,q,c = map(int,input().split())
    graph[(p,0)].append((p,c))
    graph[(p,c)].append((p,0))
    graph[(q,0)].append((q,c))
    graph[(q,c)].append((q,0))
    graph[(p,c)].append((q,c))
    graph[(q,c)].append((p,c))

INF = 10 ** 9
dist = defaultdict(lambda: INF)

visited = set()
q = [(1,0)] # 0 が会社に属していない状態
dist[(1,0)] = 0
d = 0
while q:
    qq = []
    while q:
        v,c = q.pop()
        if c == 0:
            for v1,c1 in graph[(v,0)]:
                if dist[(v1,c1)] <= d + 1:
                    continue
                dist[(v1,c1)] = d + 1
                qq.append((v1,c1))
        else:
            for v1,c1 in graph[(v,c)]:
                if dist[(v1,c1)] <= d:
                    continue
                dist[(v1,c1)] = d
                q.append((v1,c1))
    d += 1
    q = qq

answer = dist[(N,0)]
if answer == INF:
    answer = -1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

N,M = map(int,input().split())
PQC = [[int(x) for x in input().split()] for _ in range(M)]

U = 10 ** 6

V = set(range(1,N+1))
V |= set(p + c * U for p,q,c in PQC)
V |= set(q + c * U for p,q,c in PQC)
V = tuple(V)
v_to_i = {v:i for i,v in enumerate(V)}

# グラフを作成
rows, cols = [],[]
rows += [i for i,pc in enumerate(V) if pc > U]
cols += [v_to_i[pc % U] for i,pc in enumerate(V) if pc > U]
wt = [1] * len(rows)
rows += [v_to_i[p + c * U] for p,q,c in PQC]
cols += [v_to_i[q + c * U] for p,q,c in PQC]
wt += [0] * M

graph = csr_matrix((wt, (rows, cols)), (len(V), len(V)))

start = v_to_i[1]
goal = v_to_i[N]

dist = dijkstra(graph, directed = False, indices = start)[goal]

answer = -1 if dist == float('inf') else int((dist + 1)//2)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

N,M = map(int,input().split())
PQC = [[int(x) for x in input().split()] for _ in range(M)]

V = set((x,0) for x in range(1,N+1))
V |= set((p,c) for p,q,c in PQC)
V |= set((q,c) for p,q,c in PQC)
V = list(V)
v_to_i = {v:i for i,v in enumerate(V)}

# グラフを作成
rows, cols = [],[]
rows += [i for i,(p,c) in enumerate(V) if c != 0]
cols += [v_to_i[(p,0)] for i,(p,c) in enumerate(V) if c != 0]
wt = [1] * len(rows)
rows += [v_to_i[(p,c)] for p,q,c in PQC]
cols += [v_to_i[(q,c)] for p,q,c in PQC]
wt += [0] * M

graph = csr_matrix((wt, (rows, cols)), (len(V), len(V)))

start = v_to_i[(1,0)]
goal = v_to_i[(N,0)]

dist = dijkstra(graph, directed = False, indices = start)[goal]

answer = -1 if dist == float('inf') else int((dist + 1)//2)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

"""
(駅、会社)を頂点にグラフを持つ。頂点数O(M)。
そのまま辺を貼ると辺が多くなりすぎる。
(駅、会社) -> (駅、無属性) -> (駅、会社)
"""

N,M = map(int,input().split())
PQC = [[int(x) for x in input().split()] for _ in range(M)]

V = set((x,0) for x in range(1,N+1))
V |= set((p,c) for p,q,c in PQC)
V |= set((q,c) for p,q,c in PQC)
V = list(V)
v_to_i = {v:i for i,v in enumerate(V)}

# グラフを作成
rows = []
cols = []
wt = []
for i,(p,c) in enumerate(V):
    if c != 0:
        j = v_to_i[(p,0)]
        rows.append(i)
        cols.append(j)
        wt.append(1)
for p,q,c in PQC:
    i = v_to_i[(p,c)]
    j = v_to_i[(q,c)]
    rows.append(i)
    cols.append(j)
    wt.append(0)

graph = csr_matrix((wt, (rows, cols)), (len(V), len(V)))

start = v_to_i[(1,0)]
goal = v_to_i[(N,0)]

dist = dijkstra(graph, directed = False, indices = start)[goal]

answer = -1 if dist == float('inf') else int((dist + 1)//2)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys, heapq
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		#self.dist = [float("inf") for _ in range(self.size)]
		self.dist = defaultdict(lambda :10**30)
		self.dist[self.start] = 0
		#self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v, w in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					#self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

n, m = map(int, input().split())
cost = [10**30 for _ in range(n)]
edges = defaultdict(list)
for _ in range(m):
	p, q, t = map(int, input().split())
	edges[p-1 + t * n].append([q-1 + t * n, 0])
	edges[q-1 + t * n].append([p-1 + t * n, 0])
	if len(edges[p-1 + t * n]) == 1:
		edges[p-1 + t * n].append([p-1 + 0 * n, 0])
		edges[p-1 + 0 * n].append([p-1 + t * n, 1])
	if len(edges[q-1 + t * n]) == 1:
		edges[q-1 + t * n].append([q-1 + 0 * n, 0])
		edges[q-1 + 0 * n].append([q-1 + t * n, 1])

d = DijkstraList(edges, 0)
d.solve()
res = d.distance(n-1)
if res > 10**20:
	print(-1)
else:
	print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys, heapq
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		#self.dist = [float("inf") for _ in range(self.size)]
		self.dist = defaultdict(lambda :10**30)
		self.dist[self.start] = 0
		#self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v, w in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					#self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

n, m = map(int, input().split())
cost = [10**30 for _ in range(n)]
used = defaultdict(lambda: False)
edges = defaultdict(list)
for _ in range(m):
	p, q, t = map(int, input().split())
	edges[p-1 + t * n].append([q-1 + t * n, 0])
	edges[q-1 + t * n].append([p-1 + t * n, 0])
	if used[p-1 + t * n] == False:
		edges[p-1 + t * n].append([p-1 + 0 * n, 0])
		edges[p-1 + 0 * n].append([p-1 + t * n, 1])
	if used[q-1 + t * n] == False:
		edges[q-1 + t * n].append([q-1 + 0 * n, 0])
		edges[q-1 + 0 * n].append([q-1 + t * n, 1])
	used[p-1 + t * n] = True
	used[q-1 + t * n] = True

#print(edges.items())
d = DijkstraList(edges, 0)
d.solve()
res = d.distance(n-1)
if res > 10**20:
	print(-1)
else:
	print(res)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import defaultdict
  from heapq import heappush,heappop,heapify
  from bisect import bisect_left
  B=bisect_left
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  if not t:
    print(-1)
    exit()
  z=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    z.extend([a,b,a+n*c,b+n*c])
  z=sorted(set(z))
  edge=[[]for _ in z]
  d={}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    i,j,x,y=B(z,a),B(z,b),B(z,a+n*c),B(z,b+n*c)
    if b==n:
      l.append(y)
      d[y]=inf
    edge[i].append((1,x))
    edge[j].append((1,y))
    edge[x].extend([(0,i),(0,y)])
    edge[y].extend([(0,j),(0,x)])
  used=[True]*len(z)
  used[0]=False
  edgelist=edge[0]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from array import array
  from collections import defaultdict
  from heapq import heappush,heappop,heapify
  A=array
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  edge=defaultdict(list)
  used,d={},{}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    x,y=a+n*c,b+n*c
    if b==n:
      l.append(y)
      d[y]=inf
    edge[a].append(A('L',[1,x]))
    edge[b].append(A('L',[1,y]))
    edge[x].extend([A('L',[0,a]),A('L',[0,y])])
    edge[y].extend([A('L',[0,b]),A('L',[0,x])])
    used[a]=used[b]=used[x]=used[y]=True
  used[1]=False
  edgelist=edge[1]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,A('L',[e[0]+m[0],e[1]]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import defaultdict
  from heapq import heappush,heappop,heapify
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  edge=defaultdict(list)
  used,d={},{}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    x,y=a+n*c,b+n*c
    if b==n:
      l.append(y)
      d[y]=inf
    edge[a].append((1,x))
    edge[b].append((1,y))
    edge[x].extend([(0,a),(0,y)])
    edge[y].extend([(0,b),(0,x)])
    used[a]=used[b]=used[x]=used[y]=True
  used[1]=False
  edgelist=edge[1]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappush,heappop,heapify
inf=2**31-1
n,m,*t=map(int,open(0).read().split())
edge=defaultdict(list)
used,d={},{}
l=[]
for a,b,c in zip(t[::3],t[1::3],t[2::3]):
  if b<a:a,b=b,a
  x,y=a+n*c,b+n*c
  if b==n:
    l.append(y)
    d[y]=inf
  edge[a].append((1,x))
  edge[b].append((1,y))
  edge[x].extend([(0,a),(0,y)])
  edge[y].extend([(0,b),(0,x)])
  used[a]=used[b]=used[x]=used[y]=True
used[1]=False
edgelist=edge[1]
heapify(edgelist)
while edgelist:
  m=heappop(edgelist)
  if not used[m[1]]:
    continue
  d[m[1]]=m[0]
  used[m[1]]=False
  for e in edge[m[1]]:
    if used[e[1]]:
      heappush(edgelist,(e[0]+m[0],e[1]))
a=min([d[i]for i in l]or[inf])
print([a,-1][a==inf])

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  from collections import defaultdict
  from heapq import heappush,heappop,heapify
  input=sys.stdin.readline
  inf=2**31-1
  n,m=map(int,input().split())
  edge=defaultdict(list)
  used=defaultdict(bool)
  d={}
  l=[]
  for _ in range(m):
    a,b,c=map(int,input().split())
    if b<a:a,b=b,a
    x,y=a+n*c,b+n*c
    if b==n:
      l.append(y)
      d[y]=inf
    edge[a].append((1,x))
    edge[b].append((1,y))
    ex,ey=edge[x].append,edge[y].append
    ex((0,a))
    ex((0,y))
    ey((0,b))
    ey((0,x))
  used[1]=True
  edgelist=edge[1]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if used[m[1]]:continue
    d[m[1]]=m[0]
    used[m[1]]=True
    for e in edge[m[1]]:
      if used[e[1]]:continue
      heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import defaultdict
  from heapq import heappush,heappop,heapify
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  edge=defaultdict(list)
  used=defaultdict(bool)
  d={}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    x,y=a+n*c,b+n*c
    if b==n:
      l.append(y)
      d[y]=inf
    edge[a].append((1,x))
    edge[b].append((1,y))
    ex,ey=edge[x].append,edge[y].append
    ex((0,a))
    ex((0,y))
    ey((0,b))
    ey((0,x))
  used[1]=True
  edgelist=edge[1]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=True
    for e in edge[m[1]]:
      if not used[e[1]]:
        heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import defaultdict
  from heapq import heappush,heappop
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  edge=defaultdict(list)
  used,d={},{}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    x,y=a+n*c,b+n*c
    if b==n:
      l.append(y)
      d[y]=inf
    edge[a].append((1,x))
    edge[b].append((1,y))
    ex,ey=edge[x].append,edge[y].append
    ex((0,a))
    ex((0,y))
    ey((0,b))
    ey((0,x))
    used[a]=used[b]=used[x]=used[y]=True
  used[1]=False
  edgelist=[]
  for e in edge[1]:
    heappush(edgelist,e)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import defaultdict
  from heapq import heappush,heappop
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  edge=defaultdict(list)
  used,d={},{}
  l=set()
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    x,y=a+n*c,b+n*c
    if b==n:l|={y}
    edge[a].append((1,x))
    edge[b].append((1,y))
    ex,ey=edge[x].append,edge[y].append
    ex((0,a))
    ex((0,y))
    ey((0,b))
    ey((0,x))
    used[a]=used[b]=used[x]=used[y]=True
    d[y]=inf
  used[1]=False
  edgelist=[]
  for e in edge[1]:
    heappush(edgelist,e)
  while edgelist:
    c,v=heappop(edgelist)
    if not used[v]:
      continue
    d[v]=c
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+c,e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import defaultdict
  from heapq import heappush,heappop
  inf=10**12
  n,m,*t=map(int,open(0).read().split())
  edge=defaultdict(list)
  used,d={},{}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    x,y=a+n*c,b+n*c
    if b==n:l.append(y)
    edge[a].append((1,x))
    edge[b].append((1,y))
    ex,ey=edge[x].append,edge[y].append
    ex((0,a))
    ex((0,y))
    ey((0,b))
    ey((0,x))
    used[a]=used[b]=used[x]=used[y]=True
    d[a]=d[b]=d[x]=d[y]=inf
  d[1]=0
  used[1]=False
  edgelist=[]
  for e in edge[1]:
    heappush(edgelist,e)
  while edgelist:
    c,v=heappop(edgelist)
    if not used[v]:
      continue
    d[v]=c
    used[v]=False
    for o,e in edge[v]:
      if used[e]:
        heappush(edgelist,(c+o,e))
  a=min([d[i]for i in set(l)]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from gc import collect
  from collections import defaultdict
  from heapq import heappush,heappop
  inf=10**12
  n,m,*t=map(int,open(0).read().split())
  edge=defaultdict(list)
  used,d={},{}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    x,y=a+n*c,b+n*c
    if b==n:l.append(y)
    edge[a].append((1,x))
    edge[b].append((1,y))
    ex,ey=edge[x].append,edge[y].append
    ex((0,a))
    ex((0,y))
    ey((0,b))
    ey((0,x))
    used[a]=used[b]=used[x]=used[y]=True
    d[a]=d[b]=d[x]=d[y]=inf
  d[1]=0
  del t
  collect()
  used[1]=False
  edgelist=[]
  for e in edge[1]:
    heappush(edgelist,e)
  while len(edgelist):
    minedge=heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+d[v],e[1]))
  a=min([d[i]for i in set(l)]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import defaultdict
  from heapq import heappush,heappop
  inf=10**12
  n,m,*t=map(int,open(0).read().split())
  edge=defaultdict(list)
  used,d={},{}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    x,y=a+n*c,b+n*c
    if b==n:l.append(y)
    edge[a].append((1,x))
    edge[b].append((1,y))
    ex,ey=edge[x].append,edge[y].append
    ex((0,a))
    ex((0,y))
    ey((0,b))
    ey((0,x))
    used[a]=used[b]=used[x]=used[y]=True
    d[a]=d[b]=d[x]=d[y]=inf
  for i in edge:
    edge[i]=tuple(edge[i])
  d[1]=0
  used[1]=False
  edgelist=[]
  for e in edge[1]:
    heappush(edgelist,e)
  while edgelist:
    minedge=heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+d[v],e[1]))
  a=min([d[i]for i in set(l)]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import defaultdict
  from heapq import heappush,heappop
  inf=10**12
  n,m,*t=map(int,open(0).read().split())
  edge=defaultdict(list)
  used,d={},{}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    x,y=a+n*c,b+n*c
    if b==n:l.append(y)
    edge[a].append((1,x))
    edge[b].append((1,y))
    ex,ey=edge[x].append,edge[y].append
    ex((0,a))
    ex((0,y))
    ey((0,b))
    ey((0,x))
    used[a]=used[b]=used[x]=used[y]=True
    d[a]=d[b]=d[x]=d[y]=inf
  d[1]=0
  used[1]=False
  edgelist=[]
  for e in edge[1]:
    heappush(edgelist,e)
  while len(edgelist):
    minedge=heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+d[v],e[1]))
  a=min([d[i]for i in set(l)]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import defaultdict
  from heapq import heappush,heappop
  inf=10**18
  n,m,*t=map(int,open(0).read().split())
  edge=defaultdict(list)
  used,d={},{}
  l=[]
  f=g=False
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    if a<2:f=True
    if b==n:g=True
    x,y=a+n*c,b+n*c
    if b==n:l.append(y)
    edge[a].append((1,x))
    edge[b].append((1,y))
    ex,ey=edge[x].append,edge[y].append
    ex((0,a))
    ex((0,y))
    ey((0,b))
    ey((0,x))
    used[a]=used[b]=used[x]=used[y]=True
    d[a]=d[b]=d[x]=d[y]=inf
  if not(f and g):
    print(-1)
    exit()
  d[1]=0
  used[1]=False
  edgelist=[]
  for e in edge[1]:
    heappush(edgelist,e)
  while len(edgelist):
    minedge=heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+d[v],e[1]))
  a=min(d[i]for i in set(l))
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import defaultdict
  from heapq import heappush,heappop
  inf=10**18
  n,m,*t=map(int,open(0).read().split())
  edge=defaultdict(list)
  used=defaultdict(lambda:True)
  l=[]
  f=g=False
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    if a<2:f=True
    if b==n:g=True
    x,y=a+n*c,b+n*c
    if b==n:l.append(y)
    edge[a].append((1,x))
    edge[b].append((1,y))
    ex,ey=edge[x].append,edge[y].append
    ex((0,a))
    ex((0,y))
    ey((0,b))
    ey((0,x))
  if not(f and g):
    print(-1)
    exit()
  d=defaultdict(lambda:inf)
  d[1]=0
  used[1]=False
  edgelist=[]
  for e in edge[1]:
    heappush(edgelist,e)
  while len(edgelist):
    minedge=heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+d[v],e[1]))
  a=min(d[i]for i in set(l))
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import defaultdict
  from heapq import heappush,heappop
  inf=10**18
  n,m,*t=map(int,open(0).read().split())
  e=defaultdict(list)
  s=[]
  l=[]
  f=g=False
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    if a<2:f=True
    if b==n:g=True
    x,y=a+n*c,b+n*c
    if b==n:l.append(y)
    e[a].append((1,x))
    e[b].append((1,y))
    ex,ey=e[x].append,e[y].append
    ex((0,a))
    ex((0,y))
    ey((0,b))
    ey((0,x))
    s.extend([a,b,x,y])
  if not(f and g):
    print(-1)
    exit()
  d={i:v for v,i in enumerate(sorted(set(s)))}
  l=[d[i]for i in l]
  n=len(d)
  edge=[[]for _ in range(n)]
  for i in e:
    edge[d[i]]=[(c,d[j])for c,j in e[i]]
  edge=tuple(edge)
  d=[inf]*n
  used=[True]*n
  d[0]=0
  used[0]=False
  edgelist=[]
  for e in edge[0]:
    heappush(edgelist,e)
  while len(edgelist):
    minedge=heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+d[v],e[1]))
  a=min(d[i]for i in l)
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import defaultdict
  from heapq import heappush,heappop
  inf=10**18
  n,m,*t=map(int,open(0).read().split())
  e=defaultdict(list)
  s=[]
  l=[]
  f=g=False
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    if a<2:f=True
    if b==n:g=True
    x,y=a+n*c,b+n*c
    if b==n:l.append(y)
    e[a].append((1,x))
    e[b].append((1,y))
    e[x].append((0,a))
    e[x].append((0,y))
    e[y].append((0,b))
    e[y].append((0,x))
    s.extend([a,b,x,y])
  if not(f and g):
    print(-1)
    exit()
  d={i:v for v,i in enumerate(sorted(set(s)))}
  l=[d[i]for i in l]
  n=len(d)
  edge=[[]for _ in range(n)]
  for i in e:
    edge[d[i]]=[(c,d[j])for c,j in e[i]]
  edge=tuple(edge)
  d=[inf]*n
  used=[True]*n
  d[0]=0
  used[0]=False
  edgelist=[]
  for e in edge[0]:
    heappush(edgelist,e)
  while len(edgelist):
    minedge=heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+d[v],e[1]))
  a=min(d[i]for i in l)
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import*
from heapq import*
inf=10**18
n,m,*t=map(int,open(0).read().split())
e=defaultdict(list)
s=[]
l=[]
f=g=False
for a,b,c in zip(t[::3],t[1::3],t[2::3]):
  if b<a:a,b=b,a
  if a<2:f=True
  if b==n:g=True
  x,y=a+n*c,b+n*c
  if b==n:l.append(y)
  e[a].append((1,x))
  e[b].append((1,y))
  e[x].extend([(0,a),(0,y)])
  e[y].extend([(0,b),(0,x)])
  s.extend([a,b,x,y])
if not(f and g):
  print(-1)
  exit()
d={i:v for v,i in enumerate(sorted(set(s)))}
l=[d[i]for i in l]
n=len(d)
edge=tuple([]for _ in range(n))
for i in e:
  edge[d[i]].extend([(c,d[j])for c,j in e[i]])
d=[inf]*n
used=[True]*n
d[0]=0
used[0]=False
edgelist=[]
for e in edge[0]:
  heappush(edgelist,e)
while len(edgelist):
  minedge=heappop(edgelist)
  if not used[minedge[1]]:
    continue
  v=minedge[1]
  d[v]=minedge[0]
  used[v]=False
  for e in edge[v]:
    if used[e[1]]:
      heappush(edgelist,(e[0]+d[v],e[1]))
a=min(d[i]for i in l)
print([a,-1][a==inf])

Submission status: Time Limit Exceeded

Solution code:
import sys, heapq
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		#self.dist = [float("inf") for _ in range(self.size)]
		self.dist = defaultdict(lambda :float("inf"))
		self.dist[self.start] = 0
		#self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v, w in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					#self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

n, m = map(int, input().split())
cost = [float('inf') for _ in range(n)]
used = defaultdict(lambda: False)
edges = defaultdict(list)
for _ in range(m):
	p, q, t = map(int, input().split())
	edges[p-1 + t * n].append([q-1 + t * n, 0])
	edges[q-1 + t * n].append([p-1 + t * n, 0])
	if used[p-1 + t * n] == False:
		edges[p-1 + t * n].append([p-1 + 0 * n, 0])
		edges[p-1 + 0 * n].append([p-1 + t * n, 1])
	if used[q-1 + t * n] == False:
		edges[q-1 + t * n].append([q-1 + 0 * n, 0])
		edges[q-1 + 0 * n].append([q-1 + t * n, 1])
	used[p-1 + t * n] = True
	used[q-1 + t * n] = True

#print(edges.items())
d = DijkstraList(edges, 0)
d.solve()
res = d.distance(n-1)
if res == float("inf"):
	print(-1)
else:
	print(res)