# boj.kr/18352
import sys
from collections import deque
N, M, K, X = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
distance = [0] * (N+1)
visited = [False] * (N+1)
answer = []
for _ in range(M):
s, d = map(int, sys.stdin.readline().split())
graph[s].append(d)
def bfs(graph, start, visited):
queue = deque([start])
# 현재 노드를 방문 처리
visited[start] = True
# 큐가 빌 때까지 반복
while queue:
v = queue.popleft()
if distance[v] == K:
answer.append(v)
# 아직 방문하지 않은 원소들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
distance[i] = distance[v] + 1
bfs(graph, X, visited)
print('\\n'.join(map(str, sorted(answer))) if answer else -1)
# boj.kr/18352
import sys
import heapq
N, M, K, X = map(int, sys.stdin.readline().split())
graph = {i: [] for i in range(1, N+1)}
answer = []
for _ in range(M):
s, d = map(int, sys.stdin.readline().split())
graph[s].append((d, 1))
def dijkstra(graph, start):
heap = [(0, start)]
visited = set()
while heap:
(cost, u) = heapq.heappop(heap)
if u in visited:
continue
visited.add(u)
if cost == K: # K만큼 이동했을 때 추가
answer.append(u)
for v, c in graph[u]:
if v in visited:
continue
next_item = cost + c
heapq.heappush(heap, (next_item, v))
dijkstra(graph, X)
print('\\n'.join(map(str, sorted(answer))) if answer else -1)
# boj.kr/1446
import sys
import heapq
N, D = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(D+1)]
for i in range(D+1):
graph[i].append((i+1, 1)) # 한칸 이동, 이동비용 1
for _ in range(N):
start, end, cost = list(map(int, sys.stdin.readline().split()))
if end <= D:
graph[start].append((end, cost))
def dijkstra(graph, start, end):
heap = [(0, start)]
visited = set()
while heap:
(cost, u) = heapq.heappop(heap)
if u in visited:
continue
visited.add(u)
if u == end:
return cost
for v, c in graph[u]:
if v in visited:
continue
next_item = cost + c
heapq.heappush(heap, (next_item, v))
print(dijkstra(graph, 0, D))
설명
예시