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:
from collections import defaultdict 

N,M=map(int,input().split())

if M == 0:
  print(-1)
  exit()

INF = 10**20
pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
G = defaultdict(dict)
lines = [set() for _ in range(N)]
for p,q,c in pqc:
  G[(p,c)][(q,c)] = G[(q,c)][(p,c)] = 0
  lines[p].add(c)
  lines[q].add(c)
  
for v in range(N):
  if len(lines[v])>1:
    tmp = list(lines[v])
    for i in range(len(tmp)-1):
      for j in range(i+1,len(tmp)):
        G[(v,tmp[i])][(v,tmp[j])] = G[(v,tmp[j])][(v,tmp[i])] = 1
        
def dijkstra(start = 0):
    from heapq import heappop, heappush
    d = defaultdict(lambda:INF)
    d[start] = 0
    que = []
    heappush(que, (0, start))
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]: continue
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                heappush(que, (d[u], u))
    return d

for c in lines[0]:
  G[(0,-1)][(0,c)] = 1
for c in lines[N-1]:
  G[(N-1,c)][(N-1,-1)] = 0
  
d = dijkstra((0,-1))
ans = d[(N-1,-1)]
print(ans if ans < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict

import sys

input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 7)


def main():
    N, M = map(int, input().split())
    INF = 10 ** 9
    Tree = defaultdict(lambda: [])
    for _ in range(M):
        p, q, c = map(int, input().split())
        Tree[(p, c)].append(((q, c), 0))
        Tree[(q, c)].append(((p, c), 0))
        Tree[(p, c)].append(((p, 0), 0))
        Tree[(q, c)].append(((q, 0), 0))
        Tree[(p, 0)].append(((q, c), 1))
        Tree[(q, 0)].append(((p, c), 1))

    # print(Tree)
    # # print(Tree[12])

    # dist = [INF] * N
    dist = defaultdict(lambda: INF)

    def bfs01(x, r):
        # q = deque([(x, -1)])
        q = deque()
        q.append((x, r))
        dist[(x, r)] = 0
        while q:
            u, rail = q.popleft()
            # print(u, rail)
            for (nx_node, nx_rail), cost in Tree[(u, rail)]:
                d = dist[(u, rail)] + cost
                # print(nx_node, nx_rail, d, cost, dist[(nx_node, nx_rail)])
                if d < dist[(nx_node, nx_rail)]:
                    dist[(nx_node, nx_rail)] = d
                    if cost:
                        q.append((nx_node, nx_rail))
                    else:
                        q.appendleft((nx_node, nx_rail))

    bfs01(1, 0)
    # print(dist, dist[(N, 0)])
    if dist[(N, 0)] == INF:
        print(-1)
    else:
        print(dist[(N, 0)])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict

import sys

input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 7)


def main():
    N, M = map(int, input().split())
    INF = 10 ** 18
    Tree = defaultdict(lambda: [])
    for _ in range(M):
        p, q, c = map(int, input().split())
        Tree[(p, c)].append(((q, c), 0))
        Tree[(q, c)].append(((p, c), 0))
        Tree[(p, c)].append(((p, 0), 0))
        Tree[(q, c)].append(((q, 0), 0))
        Tree[(p, 0)].append(((q, c), 1))
        Tree[(q, 0)].append(((p, c), 1))

    # print(Tree)
    # # print(Tree[12])

    # dist = [INF] * N
    dist = defaultdict(lambda: INF)

    def bfs01(x, r):
        # q = deque([(x, -1)])
        q = deque()
        q.append((x, r))
        dist[(x, r)] = 0
        while q:
            u, rail = q.popleft()
            # print(u, rail)
            for (nx_node, nx_rail), cost in Tree[(u, rail)]:
                d = dist[(u, rail)] + cost
                # print(nx_node, nx_rail, d, cost, dist[(nx_node, nx_rail)])
                if d < dist[(nx_node, nx_rail)]:
                    dist[(nx_node, nx_rail)] = d
                    if cost:
                        q.append((nx_node, nx_rail))
                    else:
                        q.appendleft((nx_node, nx_rail))

    bfs01(1, 0)
    # print(dist, dist[(N, 0)])
    if dist[(N, 0)] == INF:
        print(-1)
    else:
        print(dist[(N, 0)])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys 
from collections import deque,defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10**31
N,M = map(int,readline().split())
edges = defaultdict(list)
for i in range(M):
    p,q,c = map(int,readline().split())
    edges[(p,c)].append((q,c,0))
    edges[(q,c)].append((p,c,0))
    edges[(p,0)].append((p,c,1))
    edges[(p,c)].append((p,0,0))
    edges[(q,0)].append((q,c,1))
    edges[(q,c)].append((q,0,0))
    
dist = defaultdict(lambda:INF)
q = deque([(1,0)])
dist[(1,0)] = 0

while q:
    x,c_x = q.popleft()
    for y,c_y,cost in edges[(x,c_x)]:
        d = dist[(x,c_x)] + cost
        if d < dist[(y,c_y)]:
            dist[(y,c_y)] = d
            if d == 0:
                q.appendleft((y,c_y))
            else:
                q.append((y,c_y))
ans = dist[(N,0)]
print(ans if ans != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys 
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10**31
N,M = map(int,readline().split())
edges = [[[] for _ in range(10**6+1)] for _ in range(N+1)]
for i in range(M):
    p,q,c = map(int,readline().split())
    edges[p][c].append((q,c,0))
    edges[q][c].append((p,c,0))
    edges[p][0].append((p,c,1))
    edges[p][c].append((p,0,0))
    edges[q][0].append((q,c,1))
    edges[q][c].append((q,0,0))

dist = [[INF]*(10**6+1) for _ in range(N+1)]
q = deque([(1,0)])
dist[1][0] = 0

while q:
    x,c_x = q.popleft()
    for y,c_y,cost in edges[x][c_x]:
        d = dist[x][c_x] + cost
        if d < dist[y][c_y]:
            dist[y][c_y] = d
            if d == 0:
                q.appendleft((y,c_y))
            else:
                q.append((y,c_y))
ans = dist[N][0]
print(ans if ans != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import *
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n,m=MI()
to=defaultdict(list)
inf=10**9
dist=defaultdict(int)
home=[set() for _ in range(n)]
for u in range(n):dist[u,-1]=inf
for _ in range(m):
    u,v,c=MI1()
    to[u,c].append(v)
    to[v,c].append(u)
    home[u].add(c)
    home[v].add(c)
    dist[u,c]=dist[v,c]=inf

hp=[]
dist[0,-1]=0
heappush(hp,(0,0,-1))
while hp:
    d,u,c=heappop(hp)
    #print(d,u,c,hp,dist)
    if u==n-1:
        print(d)
        break
    if d>dist[u,c]:continue
    if c==-1:
        for nc in home[u]:
            if d+1<dist[u,nc]:
                dist[u,nc]=d+1
                heappush(hp,(d+1,u,nc))
    else:
        if d<dist[u,-1]:
            dist[u,-1]=d
            heappush(hp,(d,u,-1))
        for v in to[u,c]:
            if d>=dist[v,c]:continue
            dist[v,c]=d
            heappush(hp,(d,v,c))
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n,m=MI()
to=defaultdict(list)
inf=10**9
dist=defaultdict(int)
home=[set() for _ in range(n)]
for u in range(n):dist[u,-1]=inf
for _ in range(m):
    u,v,c=MI1()
    to[u,c].append((v,c))
    to[v,c].append((u,c))
    home[u].add(c)
    home[v].add(c)
    dist[u,c]=dist[v,c]=inf

hp=[]
dist[0,-1]=0
heappush(hp,(0,0,-1))
while hp:
    d,u,c=heappop(hp)
    #print(d,u,c,hp,dist)
    if u==n-1:
        print(d)
        break
    if d>dist[u,c]:continue
    if c==-1:
        for nc in home[u]:
            if d+1<dist[u,nc]:
                dist[u,nc]=d+1
                heappush(hp,(d+1,u,nc))
    else:
        if d<dist[u,-1]:
            dist[u,-1]=d
            heappush(hp,(d,u,-1))
        for v,_ in to[u,c]:
            if d>=dist[v,c]:continue
            dist[v,c]=d
            heappush(hp,(d,v,c))
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n,m=MI()
to=[[] for _ in range(n)]
inf=10**6
for _ in range(m):
    u,v,c=MI1()
    to[u].append((v,c))
    to[v].append((u,c))
hp=[]
dd={}
heappush(hp,(0,0,-1))
dd[0,-1]=0
while hp:
    d,u,c=heappop(hp)
    if u==n-1:
        print(d)
        break
    if d>dd[u,c]:continue
    for v,nc in to[u]:
        nd=d if c==nc else d+1
        if (v,nc) in dd and nd>=dd[v,nc]:continue
        dd[v,nc]=nd
        heappush(hp,(nd,v,nc))
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = {}
M = iter(pqc)

for p,q,c in zip(M,M,M):
    pc = ((p-1)<<20)+c
    qc = ((q-1)<<20)+c
    pp = (p-1)<<20
    qq = (q-1)<<20
    
    if pc not in g: g[pc] = []
    if qc not in g: g[qc] = []
    if pp not in g: g[pp] = []
    if qq not in g: g[qq] = []
    
    g[pc].append(qc)
    g[pc].append(pp)

    g[qc].append(pc)
    g[qc].append(qq)

    g[pp].append(pc)
    g[qq].append(qc)

if 0 not in g: g[0] = []

from collections import deque
q = deque([(0,0)])
res = {0:0}

mask = (1<<20)-1
INF = 1<<30
while q:
    vl,dv = q.popleft()
    if res[vl] < dv: continue

    for tl in g[vl]:
        cost = (vl&mask==0 or tl&mask==0)
        ndv = cost + dv
        if (tl not in res or res[tl] > ndv):
            res[tl] = ndv
            if cost: q.appendleft((tl,ndv))
            else: q.append((tl,ndv))
            

if (n-1)<<20 in res:
    print(res[(n-1)<<20]//2)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = [[] for _ in range(n)]
M = iter(pqc)

#s = [set() for _ in range(n)]
s = set()
for p,q,c in zip(M,M,M):
    p -= 1
    q -= 1
    g[p].append((q,c))
    g[q].append((p,c))
    if p==0 or q==0: s.add(c)
    #s[p].add(c)
    #s[q].add(c)
    


from collections import deque
def bfs01(g,s):
    n = len(g)
    #checked = [0]*n
    #checked[0] = 1
    ans = INF = 1<<30
    mask = (1<<20)-1
    q = deque((ci,1) for ci in s)
    res = {ci:1 for ci in s}
    
    mmm = [INF]*n
    
    #print(res)
    while q:
        vl,dv = q.popleft()
        v,l = vl>>20, vl&mask
        if res[vl] < dv or mmm[v] < dv: continue
        for to,line in g[v]:
            tl = (to<<20)+line
            ndv = dv+(0 if l==line else 1)
            if tl not in res or res[tl] > ndv and mmm[to] >= ndv:
                mmm[to] = min(mmm[to],ndv)
                res[tl] = ndv
                if l==line: q.appendleft((tl,ndv))
                else: q.append((tl,ndv))
                
                #if to == n-1: ans = min(ans,ndv)
                
                #print(tl,ndv,(v,l,dv),l==line)
    ans = mmm[-1]                
        #print(q)
    if ans==INF: ans=-1
    return ans



print(bfs01(g,s))


#print(res)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = [[] for _ in range(n)]
M = iter(pqc)

#s = [set() for _ in range(n)]
s = set()
for p,q,c in zip(M,M,M):
    p -= 1
    q -= 1
    g[p].append((q,c))
    g[q].append((p,c))
    if p==0 or q==0: s.add(c)
    #s[p].add(c)
    #s[q].add(c)
    


from collections import deque
def bfs01(g,s):
    n = len(g)
    #checked = [0]*n
    #checked[0] = 1
    ans = INF = 1<<30
    mask = (1<<20)-1
    q = deque((ci,1) for ci in s)
    res = {ci:1 for ci in s}
    
    mmm = [INF]*n
    
    #print(res)
    while q:
        vl,dv = q.popleft()
        if res[vl] < dv: continue
        v,l = vl>>20, vl&mask
        for to,line in g[v]:
            tl = (to<<20)+line
            ndv = dv+(0 if l==line else 1)
            if tl not in res or res[tl] > ndv and mmm[to] >= ndv:
                mmm[to] = min(mmm[to],ndv)
                res[tl] = ndv
                if l==line: q.appendleft((tl,ndv))
                else: q.append((tl,ndv))
                
                #if to == n-1: ans = min(ans,ndv)
                
                #print(tl,ndv,(v,l,dv),l==line)
    ans = mmm[-1]                
        #print(q)
    if ans==INF: ans=-1
    return ans



print(bfs01(g,s))


#print(res)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = [[] for _ in range(n)]
M = iter(pqc)

#s = [set() for _ in range(n)]
s = set()
for p,q,c in zip(M,M,M):
    p -= 1
    q -= 1
    g[p].append((q,c))
    g[q].append((p,c))
    if p==0 or q==0: s.add(c)
    #s[p].add(c)
    #s[q].add(c)
    


from collections import deque
def bfs01(g,s):
    n = len(g)
    #checked = [0]*n
    #checked[0] = 1
    ans = INF = 1<<30
    mask = (1<<20)-1
    q = deque((ci,1) for ci in s)
    res = {ci:1 for ci in s}
    #print(res)
    while q:
        vl,dv = q.popleft()
        if res[vl] < dv: continue
        v,l = vl>>20, vl&mask
        for to,line in g[v]:
            tl = (to<<20)+line
            ndv = dv+(0 if l==line else 1)
            if tl not in res or res[tl] > ndv:
                res[tl] = ndv
                if l==line: q.appendleft((tl,ndv))
                else: q.append((tl,ndv))
                
                if to == n-1: ans = min(ans,ndv)
                
                #print(tl,ndv,(v,l,dv),l==line)
                
        #print(q)
    if ans==INF: ans=-1
    return ans



print(bfs01(g,s))


#print(res)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = map(int, read().split())

g = [[] for _ in range(n)]
M = iter(pqc)

#s = [set() for _ in range(n)]
s = set()
for p,q,c in zip(M,M,M):
    p -= 1
    q -= 1
    g[p].append((q,c))
    g[q].append((p,c))
    if p==0 or q==0: s.add(c)
    #s[p].add(c)
    #s[q].add(c)
    


from collections import deque
def bfs01(g,s):
    n = len(g)
    #checked = [0]*n
    #checked[0] = 1

    q = deque((0,ci,1) for ci in s)
    res = {(0,ci):1 for ci in s}
    #print(res)
    while q:
        v,l,dv = q.popleft()
        for to,line in g[v]:
            tl = (to,line)
            ndv = dv+(not l==line)
            if tl not in res or res[tl] > ndv:
                res[tl] = ndv
                if l==line: q.appendleft((to,line,ndv))
                else: q.append((to,line,ndv))
                
                #print(tl,ndv,(v,l,dv),l==line)
                
        #print(q)

    return res



res = bfs01(g,s)

INF = 1<<30
ans = INF
for (v,l),val in res.items():
    if v==n-1:
        ans = min(ans,val)
        #print(v,l,val)

if ans==INF: print(-1)
else: print(ans)

#print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for _ in range(N)]
    D = dict()
    for _ in range(M):
        p, q, c = map(int, input().split())
        Edge[p-1].append((q-1, c))
        Edge[q-1].append((p-1, c))
        D[(p-1, c)] = D[(q-1, c)] = -1
    for i in range(N): D[(i, -1)] = -1
    q = []
    heappush(q, (0, 0, -1)) #cost, node, company

    while q:
        d, nn, nc = heappop(q)
        if D[(nn, nc)] == -1:
            D[(nn, nc)] = d
            if nc == -1:
                for ne, c in Edge[nn]:
                    if D[(ne, c)] == -1: heappush(q, (d+1, ne, c))
            else:
                heappush(q, (d, nn, -1))
                for ne, c in Edge[nn]:
                    if c == nc and D[(ne, c)] == -1: heappush(q, (d, ne, c))
    
    print(D[(N-1, -1)])

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict
N, M = map(int, input().split())
Rails = [[] for _ in range(N)]

def constant_factory(value): return lambda: value
Costs = defaultdict(constant_factory(1000000000))
Visited = defaultdict(constant_factory(False))

for _ in range(M):
    p, q, c = map(int, input().split())
    Rails[p-1].append((q-1, c))
    Rails[q-1].append((p-1, c))

Q = [(0, 0, -1)]
heapq.heapify(Q)
while Q:
    currentCost, currentNode, currentCompany = heapq.heappop(Q)
    if not Visited[(currentNode, currentCompany)]:
        Visited[(currentNode, currentCompany)] = True
        if currentCompany == -1:
            for nextNode, nextCompany in Rails[currentNode]:
                if not Visited[(nextNode, nextCompany)]:
                    if Costs[(nextNode, nextCompany)] > currentCost + 1:
                        Costs[(nextNode, nextCompany)] = currentCost + 1
                        heapq.heappush(Q, (currentCost + 1, nextNode, nextCompany))
        else:
            if not Visited[(currentNode, -1)]:
                if Costs[(currentNode, -1)] > currentCost:
                    Costs[(currentNode, -1)] = currentCost
                    heapq.heappush(Q, (currentCost, currentNode, -1))
            for nextNode, nextCompany in Rails[currentNode]:
                if nextCompany == currentCompany and not Visited[(nextNode, nextCompany)]:
                    if Costs[(nextNode, nextCompany)] > currentCost:
                        Costs[(nextNode, nextCompany)] = currentCost
                        heapq.heappush(Q, (currentCost, nextNode, nextCompany))
minCost = Costs[(N-1, -1)]
print(minCost if minCost < 1000000000 else -1)

Submission status: Time Limit Exceeded

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

n, m = map(int, input().split())
G = defaultdict(set)
U = 10**6
seen = set()
for _ in range(m):
  p, q, c = map(int, input().split())
  G[p+U*c].add((q+U*c, 0))
  G[q+U*c].add((p+U*c, 0))
  G[p+U*c].add((p-U, 0))
  G[q+U*c].add((q-U, 0))
  G[p-U].add((p+U*c, 1))
  G[q-U].add((q+U*c, 1))
que = deque()
que.append((1-U, 0))
while que:
  v, cnt = que.popleft()
  if v in seen:
    continue
  if v == n-U:
    print(cnt)
    exit()
  seen.add(v)
  for nv, cost in G[v]:
    if cost == 0:
      que.appendleft((nv, cnt+cost))
    else:
      que.append((nv, cnt+cost))
print(-1)

Submission status: Time Limit Exceeded

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

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
  p, q, c = map(int, input().split())
  p -= 1
  q -= 1
  G[p].append((q, c))
  G[q].append((p, c))
que = deque()
que.append((0, -1, 0))
dist = [float("inf")]*n
while que:
  v, com, cnt = que.popleft()
  if cnt > dist[v]:
    continue
  dist[v] = cnt
  for nv, ncom in G[v]:
    if ncom == com:
      que.appendleft((nv, ncom, cnt))
    else:
      que.append((nv, ncom, cnt+1))
if dist[-1] == float("inf"):
  print(-1)
else:
  print(dist[-1])

Submission status: Time Limit Exceeded

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

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
  p, q, c = map(int, input().split())
  p -= 1
  q -= 1
  G[p].append((q, c))
  G[q].append((p, c))
que = deque()
que.append((0, -1, 0))
seen = set()
ans = float("inf")
while que:
  v, com, cnt = que.popleft()
  if v == n-1:
    ans = min(ans, cnt)
    continue
  for nv, ncom in G[v]:
    if (nv, ncom) in seen:
      continue
    if ncom == com:
      seen.add((nv, ncom))
      que.appendleft((nv, ncom, cnt))
    else:
      que.append((nv, ncom, cnt+1))
if ans == float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

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

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
  p, q, c = map(int, input().split())
  p -= 1
  q -= 1
  G[p].append((q, c))
  G[q].append((p, c))
que = deque()
que.append((0, -1, 0))
seen = set()
ans = float("inf")
while que:
  v, com, cnt = que.popleft()
  if (v, com) in seen:
    continue
  if v == n-1:
    ans = min(ans, cnt)
    continue
  seen.add((v, com))
  for nv, ncom in G[v]:
    if ncom == com:
      que.appendleft((nv, ncom, cnt))
    else:
      que.append((nv, ncom, cnt+1))
if ans == float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
from collections import defaultdict
N,M=map(int,input().split())

import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  dist={}
  used=set()
  dist[s]=0
  used.add(s)

  hq_edge=[]
  for v,w in graph[s]:
    heapq.heappush(hq_edge,(w,v))

  while hq_edge:
    min_w,min_v=heapq.heappop(hq_edge)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if min_v in used:
      continue

    dist[min_v]=min_w
    used.add(min_v)
    for v,w in graph[min_v]:
      if not v in used:
        heapq.heappush(hq_edge,(min_w+w,v))

  return dist

vset=set()
for i in range(1,N+1):
  vset.add((i,-1))

vcset=set()
graph=defaultdict(list)
for _ in range(M):
  p,q,c=map(int,input().split())
  vset.add((p,c))
  vset.add((q,c))
  graph[(p,c)].append([(q,c),0])
  graph[(q,c)].append([(p,c),0])
  if not (p,c) in vcset:
    graph[(p,c)].append([(p,-1),0])
    vcset.add((p,c))
  if not (q,c) in vcset:
    graph[(q,c)].append([(q,-1),0])
    vcset.add((q,c))  
  graph[(p,-1)].append([(q,c),1])
  graph[(q,-1)].append([(p,c),1])  

vlist=list(vset)
dist=dijkstra_heap((1,-1))
#print(dist)

if not (N,-1) in dist:
  print(-1)
else:
  print(dist[(N,-1)])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
from collections import defaultdict
N,M=map(int,input().split())

import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  dist,used={},{}
  for v in vlist:
    dist[v]=float("inf")
    used[v]=False
  dist[s]=0
  used[s]=True

  hq_edge=[]
  for v,w in graph[s]:
    heapq.heappush(hq_edge,(w,v))

  while hq_edge:
    min_w,min_v=heapq.heappop(hq_edge)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if used[min_v]:
      continue

    dist[min_v]=min_w
    used[min_v]=True
    for v,w in graph[min_v]:
      if not used[v]:
        heapq.heappush(hq_edge,(min_w+w,v))

  return dist

vset=set()
for i in range(1,N+1):
  vset.add((i,-1))

vcset=set()
graph=defaultdict(list)
for _ in range(M):
  p,q,c=map(int,input().split())
  vset.add((p,c))
  vset.add((q,c))
  graph[(p,c)].append([(q,c),0])
  graph[(q,c)].append([(p,c),0])
  if not (p,c) in vcset:
    graph[(p,c)].append([(p,-1),0])
    vcset.add((p,c))
  if not (q,c) in vcset:
    graph[(q,c)].append([(q,-1),0])
    vcset.add((q,c))  
  graph[(p,-1)].append([(q,c),1])
  graph[(q,-1)].append([(p,c),1])  

vlist=list(vset)
dist=dijkstra_heap((1,-1))
#print(dist)

if dist[(N,-1)]==float("inf"):
  print(-1)
else:
  print(dist[(N,-1)])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N,M=map(int,input().split())

import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  dist,prev,used={},{},{}
  for v in vlist:
    dist[v]=float("inf")
    prev[v]=-1
    used[v]=False
  dist[s]=0
  used[s]=True

  hq_edge=[]
  for v,w in graph[s]:
    heapq.heappush(hq_edge,(w,v,s))

  while hq_edge:
    min_w,min_v,u=heapq.heappop(hq_edge)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if used[min_v]:
      continue

    dist[min_v]=min_w
    prev[min_v]=u
    used[min_v]=True
    for v,w in graph[min_v]:
      if not used[v]:
        heapq.heappush(hq_edge,(min_w+w,v,min_v))

  return dist,prev

vset=set()
for i in range(1,N+1):
  vset.add((i,-1))

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

vlist=list(vset)
dist,prev=dijkstra_heap((1,-1))
#print(dist)

if dist[(N,-1)]==float("inf"):
  print(-1)
else:
  print(dist[(N,-1)])

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    def Dijkstra(s, g):
        from collections import deque
        d = {s}
        queue = deque()
        for q in edge[s]:
            queue.append(q)
        while queue:
            dist, point = queue.popleft()
            if point in d:
                continue
            d.add(point)
            if point == g:
                return dist
            for nextdist, nextp in edge[point]:
                if not nextp in d:
                    if nextdist:
                        queue.append((dist + 1, nextp))
                    else:
                        queue.appendleft((dist, nextp))
        return -1
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, m = map(int, input().split())
    edge = defaultdict(set)
    for _ in range(m):
        p, q, c = map(int, input().split())
        p, q = p - 1, q - 1
        edge[(p, c)].add((0, (q, c)))
        edge[(q, c)].add((0, (p, c)))
        edge[(p, c)].add((0, (p, -1)))
        edge[(q, c)].add((0, (q, -1)))
        edge[(p, -1)].add((1, (p, c)))
        edge[(q, -1)].add((1, (q, c)))
    print(Dijkstra((0, -1), (n - 1, -1)))


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    def Dijkstra(s, g):
        import heapq
        d = {s}
        queue = []
        for q in edge[s]:
            heapq.heappush(queue, q)
        while queue:
            dist, point = heapq.heappop(queue)
            q = [point]
            while q:
                point = q.pop()
                if point in d:
                    continue
                d.add(point)
                if point == g:
                    return dist
                for nextdist, nextp in edge[point]:
                    if not nextp in d:
                        if nextdist:
                            heapq.heappush(queue, (dist + 1, nextp))
                        else:
                            q.append(nextp)
        return -1
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, m = map(int, input().split())
    edge = defaultdict(set)
    for _ in range(m):
        p, q, c = map(int, input().split())
        p, q = p - 1, q - 1
        edge[(p, -1)].add((1, (p, c)))
        edge[(q, -1)].add((1, (q, c)))
        edge[(p, c)].add((0, (p, -1)))
        edge[(q, c)].add((0, (q, -1)))
        edge[(p, c)].add((0, (q, c)))
        edge[(q, c)].add((0, (p, c)))
    print(Dijkstra((0, -1), (n - 1, -1)))


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    def Dijkstra(s, g):
        import heapq
        d = {}
        d[s] = 0
        queue = []
        for q in edge[s]:
            heapq.heappush(queue, q)
        while queue:
            dist, point = heapq.heappop(queue)
            q = [point]
            while q:
                point = q.pop()
                if point in d:
                    continue
                d[point] = dist
                if point == g:
                    return dist
                for nextdist, nextp in edge[point]:
                    if not nextp in d:
                        if nextdist == 0:
                            q.append(nextp)
                        else:
                            heapq.heappush(queue, (dist + nextdist, nextp))
        return -1
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, m = map(int, input().split())
    edge = defaultdict(set)
    for _ in range(m):
        p, q, c = map(int, input().split())
        p, q = p - 1, q - 1
        edge[(p, -1)].add((1, (p, c)))
        edge[(q, -1)].add((1, (q, c)))
        edge[(p, c)].add((0, (p, -1)))
        edge[(q, c)].add((0, (q, -1)))
        edge[(p, c)].add((0, (q, c)))
        edge[(q, c)].add((0, (p, c)))
    print(Dijkstra((0, -1), (n - 1, -1)))


if __name__ == '__main__':
    resolve()