[BaekJoon] 18352번 : 특정 거리의 도시 찾기

18352번 : 특정 거리의 도시 찾기

특정 노드에서의 모든 노드에 대한 최단거리를 찾는 문제이다.

노드의 개수가 최대 300,000 개 이기 때문에 플로이드-워셜은 사용할 수 없다.

때문에 다익스트라를 사용하면 된다.

다익스트라를 통해 X 노드의 모든 노드에 대한 최단거리를 계산하고 최단거리가 K 인 노드를 출력한다.

---

import sys
import heapq


def dijkstra(graph, start, N):
	distance = [float('inf')] * (N + 1)
	distance[start] = 0
	queue = []
	heapq.heappush(queue, [0, start])

	while queue:
		dist, now = heapq.heappop(queue)
		if distance[now] < dist:
			continue

		for i in graph[now]:
			cost = dist + i[1]
			if cost < distance[i[0]]:
				distance[i[0]] = cost
				heapq.heappush(queue, [cost, i[0]])

	return distance


def solution(N, M, K, X):
	graph = {i + 1: [] for i in range(N)}
	for _ in range(M):
		start, end = map(int, sys.stdin.readline().rsplit())
		graph[start].append([end, 1])

	dists = dijkstra(graph, X, N)
	no_answer = True
	for idx, dist in enumerate(dists):
		if dist == K:
			no_answer = False
			print(idx)

	if no_answer:
		print(-1)


if __name__ == '__main__':
	N, M, K, X = map(int, input().split())
	solution(N, M, K, X)