6133 : 최단 경로 경유지
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
무방향 그래프와 세 노드 S, V, T가 주어집니다. 시작 노드 S에서 경유지 노드 V를 반드시 거쳐 도착 노드 T로 이동할 때의 최단 거리를 구하는 프로그램을 작성하십시오.
입력 설명
첫째 줄에 정점의 개수 N과 간선의 개수 M (1 ≤ N, M ≤ 1,000)이 주어집니다.
둘째 줄부터 M개의 줄에 간선 정보 u v가 주어집니다.
마지막 줄에는 시작 S, 경유지 V, 도착 T 노드 번호가 공백 구분되어 주어집니다.
둘째 줄부터 M개의 줄에 간선 정보 u v가 주어집니다.
마지막 줄에는 시작 S, 경유지 V, 도착 T 노드 번호가 공백 구분되어 주어집니다.
출력 설명
S에서 V를 거쳐 T로 가는 최단 거리를 출력합니다. 경로가 없으면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 2
1 2
2 3
1 2 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
S에서 V까지의 최단 거리를 구하는 BFS와, V에서 T까지의 최단 거리를 구하는 BFS를 각각 한 번씩 독립적으로 수행하여 두 거리 값을 합산하십시오.