Problem:


Score : 500 points

Problem Statement

Ken loves ken-ken-pa (Japanese version of hopscotch). Today, he will play it on a directed graph G.
G consists of N vertices numbered 1 to N, and M edges. The i-th edge points from Vertex u_i to Vertex v_i.

First, Ken stands on Vertex S. He wants to reach Vertex T by repeating ken-ken-pa. In one ken-ken-pa, he does the following exactly three times: follow an edge pointing from the vertex on which he is standing.

Determine if he can reach Vertex T by repeating ken-ken-pa. If the answer is yes, find the minimum number of ken-ken-pa needed to reach Vertex T. Note that visiting Vertex T in the middle of a ken-ken-pa does not count as reaching Vertex T by repeating ken-ken-pa.

Constraints

2 \leq N \leq 10^5

0 \leq M \leq \min(10^5, N (N-1))

1 \leq u_i, v_i \leq N(1 \leq i \leq M)

u_i \neq v_i (1 \leq i \leq M)

If i \neq j, (u_i, v_i) \neq (u_j, v_j).

1 \leq S, T \leq N

S \neq T

Input

Input is given from Standard Input in the following format:

N M
u_1 v_1
:
u_M v_M
S T

Output

If Ken cannot reach Vertex T from Vertex S by repeating ken-ken-pa, print -1.
If he can, print the minimum number of ken-ken-pa needed to reach vertex T.

Sample Input 1

4 4
1 2
2 3
3 4
4 1
1 3

Sample Output 1

2

Ken can reach Vertex 3 from Vertex 1 in two ken-ken-pa, as follows: 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 in the first ken-ken-pa, then 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 in the second ken-ken-pa. This is the minimum number of ken-ken-pa needed.

Sample Input 2

3 3
1 2
2 3
3 1
1 2

Sample Output 2

-1

Any number of ken-ken-pa will bring Ken back to Vertex 1, so he cannot reach Vertex 2, though he can pass through it in the middle of a ken-ken-pa.

Sample Input 3

2 0
1 2

Sample Output 3

-1

Vertex S and Vertex T may be disconnected.

Sample Input 4

6 8
1 2
2 3
3 4
4 5
5 1
1 4
1 5
4 6
1 6

Sample Output 4

2



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


Sample output:
2

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        d:int
            cost
        directed:bool
            there is direction
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        """
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        Parameters
        ----------
        s:int
            start node

        Return
        ----------
        d:dict(int:int)
            shortest cost from start node to each node 
            {to : cost}

        prev:dict(int:int)
            previous node on the shortest path
            {from : to}
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s)) # (cost, 探索候補ノード)
        v = collections.defaultdict(bool) # 確定済かどうか
        while len(q):
            # ノードuにおけるコストはk
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]: # cost is ud from u to uv
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev
n, m = inpl()
graph=Dijkstra()
for i in range(m):
    u, v = inpl()
    graph.add(u,v+n,1,directed=True)
    graph.add(u+n,v+n+n,1,directed=True)
    graph.add(u+n+n,v,1,directed=True)
s,t=inpl()
ans = 0
d, _ = graph.Dijkstra_search(s)
ans = d[t] if d[t] != INF else - 1
# print(d)
print(ans//3)

Submission status: Accepted

Solution code:
inf=10**12
n,m=map(int,input().split())
node=[[]for _ in range(n)]
dis=[inf]*(n*3)
for _ in range(m):
	a,b=map(int,input().split())
	node[a-1].append(b-1)
s,t=map(int,input().split())
dis[(s-1)*3]=0
from collections import deque
queue=deque([(s-1)*3])
while queue:
	r=queue.popleft()
	p=(r%3+1)%3
	for x in node[r//3]:
		if dis[x*3+p]==inf:
			dis[x*3+p]=dis[r]+1
			queue.append(x*3+p)
print(dis[(t-1)*3]//3 if dis[(t-1)*3]!=inf else -1)

Submission status: Accepted

Solution code:


from collections import deque


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



es = [[] for _ in range(3*N)]
for _ in range(M):
    u,v = map(int, input().split())
    u,v = u-1, v-1
    es[u].append(N + v)
    es[N + u].append(2*N + v)
    es[2*N + u].append(v)

S,T = map(int, input().split())

q = deque()
q.append(S-1)
INF = float("inf")
dist = [INF] * (3*N)
dist[S-1] = 0

while q:
    curr = q.popleft()
    
    for nxt in es[curr]:
        if dist[nxt] == INF:
            dist[nxt] = dist[curr] + 1
            if nxt == T-1:
                print(dist[nxt] // 3)
                
                exit()
            
            q.append(nxt)

print(-1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

n, m = map(int, readline().split())
graph = [[] for _ in range(n * 3)]
for i in range(m):
    u, v = map(int, readline().split())
    u -= 1
    v -= 1
    graph[u].append(v + n)
    graph[u + n].append(v + 2 * n)
    graph[u + 2 * n].append(v)
s, t = map(lambda x: int(x) - 1, readline().split())
inf = float('inf')
q = deque([s])
dist = [inf] * (3 * n)
dist[s] = 0

while q:
    now = q.popleft()
    for next in graph[now]:
        if dist[next] != inf:
            continue
        dist[next] = dist[now] + 1
        if next == t:
            print(dist[next] // 3)
            exit()
        q.append(next)
print(-1)

Submission status: Accepted

Solution code:
import queue
N, M = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)

S, T = map(int, input().split())
S -= 1
T -= 1

INF = 1001001001
dist = [[0] * 3 for _ in range(100005)]

for i in range(N):
    for j in range(3):
        dist[i][j] = INF

q = queue.Queue()
q.put((S, 0))
dist[S][0] = 0
while not q.empty():
    e = q.get()
    v = e[0]
    l = e[1]
    for u in edges[v]:
        nl = (l + 1) % 3
        if dist[u][nl] != INF:
            continue
        dist[u][nl] = dist[v][l] + 1
        q.put((u, nl))

ans = dist[T][0]
if ans == INF:
    ans = -1
else:
    ans //= 3
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
edges=[list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
S,T = map(lambda x:int(x)-1,input().split())

N3=N*3
adj=[set() for _ in range(N3)]

for a,b in edges:
    for i in range(3):
        start = a+N*i
        dst = b+N*(i+1)
        adj[start%N3].add(dst%N3)


Q=[S]
visited={S}
dist=[-1]*N3
dist[S]=0

while Q:
    tmp=[]
    for q in Q:
        for i in adj[q]:
            if i in visited:
                continue
            else:
                dist[i]=dist[q]+1
                visited.add(i)
                tmp.append(i)
    Q = tmp
print(dist[T] if dist[T]==-1 else dist[T]//3)

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,M = map(int,input().split())
UV = [tuple(map(int,input().split())) for _ in range(M)]
S,T = map(int,input().split())

S,T = S-1,T-1

E = [[] for i in range(3*N)]
for u,v in UV:
    u,v = u-1,v-1
    E[u].append(v+N)
    E[u+N].append(v+2*N)
    E[u+2*N].append(v)

from collections import deque
dq = deque([S])
inf = float("inf")
dist = [inf]*(3*N)
dist[S] = 0

while dq:
    v = dq.popleft()
    for e in E[v]:
        if dist[e] != inf:
            continue
        dist[e] = dist[v]+1
        if e==T:
            print(dist[e]//3)
            sys.exit()
        dq.append(e)

print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    # n, m = mi()
    # inv_adj = [set() for _ in range(n)]
    # inv_dist_2 = [set() for _ in range(n)]
    # inv_hopstepjump = [set() for _ in range(n)]

    # for _ in range(m):
    #     u, v = mi_0()
    #     inv_adj[v].add(u)
    
    # for i in range(n):
    #     for s in inv_adj[i]:
    #         inv_dist_2[i] |= inv_adj[s]
        
    # for i in range(n):
    #     for s in inv_dist_2[i]:
    #         inv_hopstepjump[i] |= inv_adj[s]

    # start, goal = mi_0()

    # appeared_vertice_set = set([goal])
    # q = deque([(goal, 0)])
    # while q:
    #     # print(q)
    #     u, turn = q.popleft()
    #     if turn >= n:
    #         break
    #     if u == start:
    #         print(turn)
    #         exit()
    #     for v in inv_hopstepjump[u]:
    #         if v not in appeared_vertice_set:
    #             appeared_vertice_set.add(v)
    #             q.append((v, turn + 1))
    # print(-1)

    """
    set を作るところで最悪 O(n^2) より 2 つくらい TLE
    経路長 3 の倍数というところで start からの経由数の剰余 (mod 3) を管理する、という方針は思いついたが... それをノードを増やすことで管理するという発想に至らず。
    """
    n, m = mi()
    adj = [[] for _ in range(n * 3)]
    for _ in range(m):
        a, b = mi_0()
        adj[a * 3].append(b * 3 + 1)
        adj[a * 3 + 1].append(b * 3 + 2)
        adj[a * 3 + 2].append(b * 3)
    
    start, goal = mi_0()
    start *= 3
    goal *= 3

    q = deque([(start, 0)])
    visited = [False] * (n * 3)
    while q:
        u, dist = q.popleft()
        if dist > 3 * n:
            break
        if u == goal:
            assert (dist % 3 == 0)
            print(dist // 3)
            return
        if not visited[u]:
            visited[u] = True
            for v in adj[u]:
                if not visited[v]:
                    q.append((v, dist + 1))
    print(-1)

        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
G=[[] for i in range(n)]
for i in range(m):
  u,v=map(int,input().split())
  G[u-1].append(v-1)

s,t=map(int,input().split())
s-=1
t-=1
from collections import deque
dist=[[-1]*3 for i in range(n)]
dist[s][0]=0
q=deque()
q.append([s,0])
while q:
  cur,parity=q.popleft()
  for nx in G[cur]:
    nx_parity=(parity+1)%3
    if dist[nx][nx_parity]==-1:
      dist[nx][nx_parity]=dist[cur][parity]+1
      q.append([nx,nx_parity])
if dist[t][0]==-1:
  print(-1)
else:
  print(int(dist[t][0]//3))

Submission status: Accepted

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

for i in range(M):
    u,v = list(map(int,input().split()))
    g[u].append(N + v)
    g[N + u].append(2*N + v)
    g[2*N + u].append(v)
S,T= map(int,input().split())

dq = deque([S])
inf = 10**15
d = [inf for i in range(3*N+1)]
d[S] = 0

while dq:
    v = dq.popleft()
    for nv in g[v]:
        if d[nv] > d[v] + 1:
            d[nv] = d[v] + 1
            dq.append(nv)

if inf == d[T]:
    print(-1)
else:
    print(d[T]//3)

Submission status: Accepted

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

graph=[[] for _ in range(N+1)]
for i in range(M):
  u,v=map(int,input().split())
  graph[u].append(v)
  
S,T=map(int,input().split())

#print(graph)
visited=[]
for i in range(N+1):
  visited.append([False]*3)
  
queue=[S]
t=0
while queue:
  new_queue=set()
  for u in queue:
    if u==T and t%3==0:
      print(t//3)
      sys.exit(0)
    
    visited[u][t%3]=True
    for v in graph[u]:
      if not visited[v][(t+1)%3]:
        new_queue.add(v)
        
  queue=list(new_queue)
  t+=1
  
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
path = [set() for _ in range(n)]
for _ in range(m):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    path[u].add(v)

s,t = map(int,input().split())

que = deque([(s-1,0)])
d = [[float('inf')]*n for _ in range(3)]
d[0][s-1] = 0
while que:
    p,i = que.popleft()
    j = (i+1)%3
    for to in path[p]:
        if d[j][to] == float('inf'):
            d[j][to] = d[i][p] + 1
            que.append((to,j))
if d[0][t-1] == float('inf'):
    d[0][t-1] = -3
print(d[0][t-1]//3)

Submission status: Accepted

Solution code:
import heapq
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
INF = 10**18
edge = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    edge[x-1].append(y-1)
s,t = map(int,input().split())

def dijkstra_heap(s,g,p):
    d = [[INF] * p for i in range(n)] 
    used = [[True] * p for i in range(n)] 
    used[s][0] = False
    ed_list = []
    for es in edge[s]:
        heapq.heappush(ed_list,[1,es,1]) # 回数、向かう頂点、あまり
    while len(ed_list):
        ken,v,md = heapq.heappop(ed_list)
        if not used[v][md]:
            continue
        d[v][md] = ken
        used[v][md] = False
        if not used[g][0]:
            break
        for e in edge[v]:
            if used[e][(md+1)%p]:
              if (md+1)%p == 1:
                heapq.heappush(ed_list,[ken+1,e,1])
              else:
                heapq.heappush(ed_list,[ken,e,(md+1)%p])
    return d[g][0]

ans = dijkstra_heap(s-1,t-1,3)
if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, m, *uv, s, t = map(int, read().split())
m = iter(uv)
UV = zip(m, m)
graph = [[] for _ in range(3 * n)]
for u, v in UV:
    u -= 1
    v -= 1
    graph[u].append(v + n)
    graph[u + n].append(v + 2 * n)
    graph[u + 2 * n].append(v)
s -= 1
t -= 1
infi = 10 ** 20
dist = [-1] * (3 * n)


def bfs(s):
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        v = que.popleft()
        if v == t:
            return dist[t]
        d = dist[v]
        for u in graph[v]:
            if dist[u] > 0:
                continue
            dist[u] = d + 1
            que.append(u)
    return -1


ans = bfs(s)
if ans > 0:
    ans //= 3
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, M: int, G, S: int, T: int):
    S -= 1
    T -= 1
    now = deque([S])
    dist = [0 for _ in range(N * 3)]
    while now:
        p = now.popleft()
        for n in G[p]:
            if dist[n] != 0:
                continue
            dist[n] = dist[p] + 1
            if n == T:
                print(dist[n] // 3)
                exit()
            now.append(n)
    print(-1)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    G = tuple(set() for _ in range(N * 3))
    for _ in range(M):
        u, v = int(next(tokens)) - 1, int(next(tokens))-1
        G[u].add(v + N)
        G[u + N].add(v + 2 * N)
        G[u + 2 * N].add(v)

    S = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    solve(N, M, G, S, T)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)
    s,t = map(int, input().split())
    s -= 1
    t -= 1

    d1 = [inf]*n
    d2 = [inf]*n
    d0 = [inf]*n
    d0[s] = 0
    d = deque([[s, 0]])
    while d:
        v, hosuu = d.popleft()
        hosuu += 1
        for nv in adj[v]:
            if hosuu%3==1 and d1[nv]>hosuu:
                d1[nv] = hosuu 
                d.append([nv, hosuu])
            if hosuu%3==2 and d2[nv]>hosuu:
                d2[nv] = hosuu
                d.append([nv, hosuu])
            if hosuu%3==0 and d0[nv]>hosuu:
                d0[nv] = hosuu
                d.append([nv, hosuu])
    if d0[t]==inf:
        print(-1)
    else:
        print(d0[t]//3)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
graph = [[] for _ in range(3*N)]
for _ in range(M):
  u, v = map(lambda x:int(x)-1, input().split())
  graph[3*u] += [3*v+1]
  graph[3*u+1] += [3*v+2]
  graph[3*u+2] += [3*v]

S, T = map(lambda x:int(x)-1, input().split())

def bfs(s):
  q = deque([s])
  dist = [float('inf')]*(3*N)
  dist[s] = 0

  while q:
    u = q.popleft()
    for v in graph[u]:
      if dist[v] == float('inf'):
        q += [v]
        dist[v] = dist[u] + 1

  return dist

d = bfs(3*S)
if d[3*T] == float('inf'):
  print(-1)
else:
  print(d[3*T]//3)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

INF = float('inf')

N, M = map(int, input().split())
adjL = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    adjL[3*u+0].append(3*v+1)
    adjL[3*u+1].append(3*v+2)
    adjL[3*u+2].append(3*v+0)
S, T = map(int, input().split())
S, T = S-1, T-1

# 単一始点最短経路を求める（Dijkstra法）
def Dijkstra(adjList, vSt):
    numV = len(adjList)
    numUsed = 0
    costs = [INF] * numV
    costs[vSt] = 0
    PQ = []
    heappush(PQ, (0, vSt))
    while PQ:
        cNow, vNow = heappop(PQ)
        if cNow > costs[vNow]: continue
        numUsed += 1
        if numUsed == numV: break
        for v2 in adjList[vNow]:
            c2 = cNow + 1
            if c2 < costs[v2]:
                costs[v2] = c2
                heappush(PQ, (c2, v2))
    return costs

costs = Dijkstra(adjL, 3*S)
#print('costs:', costs)

if costs[3*T] == INF:
    print(-1)
else:
    print(costs[3*T]//3)

Submission status: Accepted

Solution code:
def bfs(g, N, s, t):
    from collections import deque

    dist = [-1] * (N * 3)
    dist[s] = 0

    dq = deque()
    dq.append(s)

    while dq:
        v = dq.popleft()
        d = dist[v]
        for u in g[v]:
            if ~dist[u]: continue
            dist[u] = d + 1
            if u == t:
                return dist[t] // 3  # TLEしたので解を見つけたら即returnに変えた
            dq.append(u)
    return -1


def main():
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N * 3))
    for _ in range(M):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v + N)
        g[u + N].add(v + N * 2)
        g[u + N * 2].add(v)

    S, T = (int(x) - 1 for x in input().split())

    ans = bfs(g, N, S, T)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
NV = 3*n
edges = [[]for _ in range(NV)]


def to_v(i, j):
    return 3*i+j


for _ in range(m):
    u, v = list(map(lambda x: int(x)-1, input().split()))
    for j in range(3):
        edges[to_v(u, j)].append(to_v(v, (j+1) % 3))
s, t = list(map(lambda x: int(x)-1, input().split()))
init_v = to_v(s, 0)
INF = 10**18
dist = [INF]*NV
dist[init_v] = 0
next_v = deque([init_v])
while next_v:
    v = next_v.popleft()
    for v2 in edges[v]:
        if dist[v2] <= dist[v]+1:
            continue
        dist[v2] = dist[v]+1
        next_v.append(v2)

print(dist[to_v(t, 0)]//3 if dist[to_v(t, 0)] != INF else -1)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
UV = [[]for _ in range(n)]
for _ in range(m):
    u, v = list(map(lambda x: int(x)-1, input().split()))
    UV[u].append(v)
s, t = list(map(lambda x: int(x)-1, input().split()))

NV = 3*n
edges = [[]for _ in range(NV)]


def to_v(i, j):
    return 3*i+j


for i in range(n):
    for i2 in UV[i]:
        for j in range(3):
            edges[to_v(i, j)].append(to_v(i2, (j+1) % 3))

init_v = to_v(s, 0)
INF = 10**18
dist = [INF]*NV
dist[init_v] = 0
next_v = deque([init_v])
while next_v:
    v = next_v.popleft()
    for v2 in edges[v]:
        if dist[v2] <= dist[v]+1:
            continue
        dist[v2] = dist[v]+1
        next_v.append(v2)

print(dist[to_v(t, 0)]//3 if dist[to_v(t, 0)] != INF else -1)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    n,m = map(int,input().split())
    G = [[] for _ in range(3*n)]
    for _ in range(m):
        u,v = map(int,input().split())
        u -= 1
        v -= 1
        for i in range(3):
            G[u*3 + i].append(v*3 + (i + 1)%3)
    
    s,g = map(int,input().split())
    s -= 1
    g -= 1

    q = deque([3*s])
    dist = [-1] * (3*n)
    dist[3*s] = 0
    while q:
        p = q.popleft()
        for e in G[p]:
            if dist[e] < 0:
                dist[e] = dist[p] + 1
                q.append(e)
                
    print(dist[3*g]//3 if dist[3*g] >= 0 else -1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda: 10 ** 18)
        self.dist[start] = 0

        self.prev = defaultdict(lambda: None)

        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

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

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]



n,m = map(int, input().split())
uv = [list(map(int, input().split())) for i in range(m)]
s,t = map(int, input().split())
g = Graph()
for u,v in uv:
  g.add_edge(u*3-3,v*3-2)
  g.add_edge(u*3-2,v*3-1)
  g.add_edge(u*3-1,v*3-3)
dist = Dijkstra(g,(s-1)*3)
ans = dist.shortest_distance((t-1)*3)
if ans == 10 ** 18:
  print(-1)
else:
  print(ans // 3)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(3*N)]
for i in range(M):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  graph[3*u].append(3*v+1)
  graph[3*u+1].append(3*v+2)
  graph[3*u+2].append(3*v)

S, T = map(int, input().split())
S -= 1; T -= 1
dist = [-1] * (3*N)
dist[3*S] = 0
d = deque([3*S])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] < 0:
      dist[child] = dist[node] + 1
      d.append(child)

if dist[3*T] > 0:
  print(dist[3*T] // 3)
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
INF = -1
dist = [[INF]*3 for _ in range(N)]
vector = [[] for _ in range(N)]

for i in range(M):
    graf1, graf2 = map(int, input().split())
    vector[graf1-1].append(graf2-1)
S, T = map(int, input().split())
S, T = S-1, T-1

# BFS
dist[S][0] = 0
q = deque()
q.append((S, 0))
while q:
    v, l = q.popleft()
    for i in vector[v]:
        new_l = (l+1)%3
        if dist[i][new_l] != INF:
            continue
        dist[i][new_l] = dist[v][l] + 1
        q.append((i, new_l))

ans = dist[T][0]
if ans == INF:
    print("-1")
else:
    print(int(ans/3))

Submission status: Accepted

Solution code:
#ABC132-E Hopscotch Addict
"""
グラフを3倍して、
ある二頂点u→vに辺が存在する時
余り0の頂点u→1の頂点v
余り1の頂点u→2の頂点v
余り2の頂点u→0の頂点v
にそれぞれ辺を張った時に、
スタート(頂点S)の余り0の頂点から、
ゴール(頂点T)の余り0への最短パスが答え。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m = map(int,readline().split())
g = [[] for _ in range(3*n)]
for i in range(m):
    x,y = map(int,readline().split())
    x,y = x-1,y-1
    g[x].append([1,y+n])
    g[x+n].append([1,y+n+n])
    g[x+n+n].append([1,y])


#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    n = len(edge)
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist): #キューから値が無くなるまで
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)

s,t = map(int,readline().split())
s,t = s-1,t-1

res = dijkstra_heap(s,g)[t]

print(-1 if res == float("inf") else res//3)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
edge = [[] for i in range(n+1)]
#edge[i] : iから出る道の[行先]の配列
for _ in range(m):
    u, v = map(int, input().split())
    edge[u].append(v)
s,t = map(int, input().split())
queue = deque()
queue.append((s, 0))
visited = [[False] * 3 for _ in range(n+1)]
while queue:
    u, d = queue.popleft()
    if visited[u][d % 3]:
        continue
    visited[u][d % 3] = True
    if d % 3 == 0 and u == t:
        print(d // 3);exit()
    for v in edge[u]:
        queue.append((v, d+1))
print(-1)

Submission status: Accepted

Solution code:
import copy
n,m = map(int,input().split())
graph = [[] for _ in range(n*3)]
for i in range(m):
  u,v = map(int,input().split())
  for j in range(3):
    graph[n*j+u-1].append((n*(j+1)+v-1)%(3*n))
s,t = map(int,input().split())
wait = [s-1]
cnt = 0
done = [0]*(3*n)
while wait:
  cnt += 1
  now = copy.copy(wait)
  wait = []
  for i in now:
    for j in graph[i]:
      if not done[j]:
        done[j] = 1
        wait.append(j)
      if j == t-1:
        print(cnt//3)
        quit()
print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def MI():
  return map(int,input().split())
def main():
  n,m=MI()
  G=[[] for _ in range(n)]
  for _ in range(m):
    u,v=MI()
    u-=1
    v-=1
    G[u].append(v)
  s,t=MI()
  s-=1
  t-=1
  
  fi=[True]*n
  se=[True]*n
  th=[True]*n
  th[s]=False

  dq=[s]
  depth=0
  
  while dq:
    depth+=1
    tank1=[]
    tank2=[]
    tank3=[]
    
    for p in dq:
      for c in G[p]:
        if fi[c]:
          fi[c]=False
          tank2.append(c)
    for p in tank2:
      for c in G[p]:
        if se[c]:
          se[c]=False
          tank3.append(c)
    for p in tank3:
      for c in G[p]:
        if th[c]:
          th[c]=False
          tank1.append(c)
        if c==t:
          print(depth)
          exit()
    dq=tank1
  print(-1)  
if __name__=='__main__':
  main()