[백준/파이썬] 18352번

📍백준 18352번 문제

https://www.acmicpc.net/problem/18352

코드

import sys
import heapq

input = sys.stdin.readline


def dijkstra(x):
    q = []
    distance[x] = 0
    heapq.heappush(q, (0, x))  # 앞이 거리, 뒤가 노드
    while q:
        dist, node = heapq.heappop(q)
        if dist > distance[node]:
            continue
        for next in graph[node]:
            d = next[1] + dist
            if d < distance[next[0]]:
                distance[next[0]] = d
                heapq.heappush(q, (d, next[0]))


# n: 도시 수, m: 도로 수 k: 거리 정보 x: 출발 도시
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n+1)]
distance = [int(1e9)] * (n+1)
flag = False
for _ in range(m):
    start, end = map(int, input().split())
    graph[start].append((end, 1))
dijkstra(x)

for i in range(len(distance)):
    if distance[i] == k:
        print(i)
        flag = True
if flag == False:
    print(-1)

풀이

다익스트라를 이용해 풀면 된다.