Algorithm

2021번: 최소 환승 경로

Doljae 2021. 8. 15. 17:16
 

2021번: 최소 환승 경로

첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다. 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다. 마지막 줄에는 출발

www.acmicpc.net

 

import sys
from collections import deque, defaultdict

r = sys.stdin.readline

node_num, flag_num = map(int, r().split())
graph = defaultdict(set)

for i in range(1, flag_num + 1):
    temp = list(map(int, r().split()))
    temp.pop()
    for node in temp:
        graph[node].add(i + node_num)
        graph[i + node_num].add(node)

start, end = map(int, r().split())
q = deque([])
q.append(start)
visited = set()
visited.add(start)
cost = {start: 0}
while q:
    cur_node = q.popleft()
    if cur_node == end:
        break

    for adj in graph[cur_node]:
        if adj not in visited:
            if adj >= node_num + 1:
                cost[adj] = cost[cur_node]
            else:
                cost[adj] = cost[cur_node] + 1
            visited.add(adj)
            q.append(adj)

if start == end:
    print(0)
else:
    print(cost[end] - 1 if end in cost else -1)