6137 : 탐색 깊이 제한
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
무방향 그래프에서 시작 S에서 목표 T로 가는 최소 탐색 깊이를 구하되, 최대 탐색 허용 범위인
Limit 제한 내에서 도달 가능한지를 판별하십시오. (6105번 반복 깊이 심화 탐색의 응용입니다.)입력 설명
첫째 줄에 N, M (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 2,000)이 주어집니다.
둘째 줄부터 M개의 줄에 간선 u v가 주어집니다.
마지막 줄에 시작 S, 목표 T, 탐색 한계 깊이 Limit이 주어집니다.
둘째 줄부터 M개의 줄에 간선 u v가 주어집니다.
마지막 줄에 시작 S, 목표 T, 탐색 한계 깊이 Limit이 주어집니다.
출력 설명
Limit 이하의 깊이 중 도달 가능한 최소 깊이를 출력합니다. 불가능하면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 4
1 2
2 3
3 4
4 5
1 4 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
반복 깊이 DFS 루프를 돌아 깊이를 0부터 Limit까지 순차적으로 시도해 가장 빠른 도달 깊이를 체크하십시오.