6141 : 탐색 종합 1
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
방향 그래프 상에서 1번 노드에서 출발하여 N번 노드로 도달하려 합니다.
그래프에는 문 정점 D와 문을 열 수 있는 열쇠 정점 K가 있습니다. K를 지나기 전에는 D를 통과할 수 없습니다. 이 조건을 만족하면서 N번 노드로 도달하는 최단 거리를 구하십시오.
그래프에는 문 정점 D와 문을 열 수 있는 열쇠 정점 K가 있습니다. K를 지나기 전에는 D를 통과할 수 없습니다. 이 조건을 만족하면서 N번 노드로 도달하는 최단 거리를 구하십시오.
입력 설명
첫째 줄에 노드 수 N (1 ≤ N ≤ 100)과 간선 수 M (1 ≤ M ≤ 1,000)이 주어집니다.
둘째 줄부터 M개의 줄에 방향 간선 u v가 주어집니다.
마지막 줄에는 열쇠 노드 K와 문 노드 D가 공백 구분되어 주어집니다.
둘째 줄부터 M개의 줄에 방향 간선 u v가 주어집니다.
마지막 줄에는 열쇠 노드 K와 문 노드 D가 공백 구분되어 주어집니다.
출력 설명
조건을 만족하면서 N번에 도착할 수 있는 최단 거리를 출력합니다. 도달할 수 없으면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4
1 2
2 4
1 3
3 4
2 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
열쇠 획득 상태(0 또는 1)를 상태 차원에 포함하여
visited[node][has_key] 방문 및 최단거리 배열로 BFS 탐색을 설계하십시오.