7210 : 합승
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
두 사람이 출발지 S에서 출발하여 각각 목적지 A, B로 가려고 합니다. 두 사람의 이동 경로 중 일부 구간을 합승하여 함께 갈 수 있을 때, 두 사람의 총 이동 비용의 합을 최소화하는 최솟값을 구하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 정점 수 N, 간선 수 M, 출발지 S, A 목적지 A, B 목적지 B가 공백으로 구분되어 주어집니다. (1 ≤ N ≤ 200)
둘째 줄부터 M개의 줄에 정점 u, v와 가중치 w가 주어집니다.
둘째 줄부터 M개의 줄에 정점 u, v와 가중치 w가 주어집니다.
출력 설명
이동 비용의 합의 최솟값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 2 1 2 3
1 2 10
2 3 10
출력 예시
COPY
복사되었습니다!
복사되었습니다!
20도움
정점 1(S)에서 출발하여 2(A), 3(B)에 도착합니다. 합승 구간을 1→2(비용 10)로 하고 이후 A는 도착, B는 2→3(비용 10)으로 이동하면 총 비용 10+10=20이 최솟값입니다.