https://www.acmicpc.net/problem/18352
난이도: 실버2
소요시간: 30분
다익스트라를 쓰면 풀리는 문제이다. 거리가 1로 고정인 점을 생각하여 다익스트라 알고리즘을 조금 수정 하면된다.
import sys
import heapq
N,M,K,X = map(int,sys.stdin.readline().split())
INF=1e9
dist = [INF]*(N+1)
graph=[[] for _ in range(N+1)]
for _ in range(M):
start_city,end_city= map(int,sys.stdin.readline().split())
graph[start_city].append(end_city)
def dijkstra(start):
q=[]
heapq.heappush(q,[0,start])
dist[start]=0
while q:
distance,node=heapq.heappop(q)
for next in graph[node]:
if dist[next]>dist[node]+1:
dist[next]=dist[node]+1
heapq.heappush(q,[dist[next],next])
result=[]
dijkstra(X)
for i in range(1,len(dist)):
if dist[i]==K:
result.append(i)
if len(result)==0:
print(-1)
else:
for r in result:
print(r)
'Problem Solving > 최단 경로' 카테고리의 다른 글
BOJ1916 최소비용 구하기 (0) | 2023.03.30 |
---|---|
BOJ1446 지름길 (0) | 2023.03.21 |
전보 (1) | 2023.01.20 |
미래도시 (0) | 2023.01.19 |