6200 : 최단 경로 + 조건
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
출발지 1에서 시작하여 반드시 거쳐야 하는 서로 다른 두 노드 v1과 v2를 모두 거쳐 도착지 N으로 가는 최단 경로의 길이를 구하시오.
입력 설명
첫째 줄에 노드의 개수 N, 간선의 개수 E (1 ≤ N, E ≤ 50,000)가 주어집니다.
둘째 줄부터 E개의 줄에 간선 정보 u, v, w가 주어집니다. (양방향 간선)
마지막 줄에 거쳐야 하는 두 노드 v1, v2가 주어집니다.
둘째 줄부터 E개의 줄에 간선 정보 u, v, w가 주어집니다. (양방향 간선)
마지막 줄에 거쳐야 하는 두 노드 v1, v2가 주어집니다.
출력 설명
v1, v2를 모두 거치는 최단 경로의 길이를 출력합니다. 불가능하면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4
1 2 3
2 3 3
3 4 1
1 3 5
2 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
7