문제
* 본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제이다.
밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 '커미'는 최근 야근이 잦아져 택시를 더 많이
이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있다. '커미'는 자신이 택시를
이용할 때 동료인 '하니' 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을
알게 되었다. '커미'는 '하니'와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을
얼마나 아낄 수 있을 지 계산해 보고 '하니'에게 합승을 제안해 보려고 한다.
위 그림은 택시가 이동 가능한 반경에 있는 6개 지점 사이의 이동 가능한 택시노선과
예상 요금을 보여주고 있다.
그림에서 커미와 하니 두 사람은 출발지점인 4번 지점에서 출발해서 택시를 타고 귀가 하려고 한다.
커의 집은 6번 지점에 있으며 하니의 집은 2번 지점에 있고 두 사람이 모두 귀가하는 데
소요되는 예상 최저 택시요금이 얼마인지 계산하려고 한다.
* 그림의 []은 지점을 나타내며 [] 안의 숫자는 지점 번호를 나타낸다.
- 지점이 n개일 때, 지점 번호는 1부터 n까지 사용된다.
* 지점 간에 택시가 이동할 수 있는 경로를 간선이라 하며,
간선에 표시된 숫자는 두 지점 사이의 예상 택시요금을 나타낸다.
- 간선은 편의 상 선으로 표시되어 있다.
- 위 그림 예시에서, 4번 지점에서 1번 지점으로(4->1)가거나,
1번 지점에서 4번 지점으로(1->4) 갈 때 예상 택시요금은 10원으로
동일하며 이동 방향에 따라 달라지지 않는다.
* 예상되는 최저 택시요금은 다음과 같이 계산된다.
- 4->1->5 : 커미와 하니가 합승하여 택시를 이용한다.
예상 택시요금은 10 + 24 = 34원이다.
- 5->6 : 커미가 혼자 택시를 이용한다. 예상 택시요금은 2원이다.
- 5->3->2 : 하니가 혼자 택시를 이용한다.
예상 택시요금은 24 + 22 = 46원이다.
- 커미와 하니 모두 귀가 완료까지 예상되는 최저 택시요금은 34+2+46 = 82원이다.
입력
첫 행에 N, S, a, b가 공백을 구분하여 주어진다.
N은 지점의 개수, S는 출발지 번호, a는 커미의 목적지, b는 하니의 목적지이다.
(3 <= N <= 200) ( 1 <= S, a, b <= N ) ( a ≠ b )
다음 행에 간선의 개수 M이 주어진다. ( 2 <= M <= N*(N-1)/2 )
다음 행부터 M개의 행에 x y c 형식의 정보가 주어진다.
x지점으로 부터 y까지 또는 y지점으로 부터 x까지의 요금이 c라는 의미이다.
( 1 <= c <= 100,000 )
두 지점간 요금에 대한 정보는 1번만 주어진다.
a, b 두 지점은 출발 지점으로부터 도달 가능하도록 주어진다.
출력
커미와 하니 두 사람이 S를 출발하여 각각 a, b에 도착할 때 최소의 비용을 구하여 출력하시오.
합승을 하지 않고 각자 이동하는 경우의 비용이 최소라면 합승을 하지 않아도 된다.
예제 #1
6 4 6 2
9
4 1 10
3 5 24
5 6 2
3 1 41
5 1 24
4 6 50
2 4 66
2 3 22
1 6 25
82
예제 #2
7 3 4 1
5
5 7 9
4 6 4
3 6 1
3 2 3
2 1 6
14
예제 #3
6 4 5 6
8
2 6 6
6 3 7
4 6 7
6 5 11
2 5 12
5 3 20
2 4 8
4 3 9
18
힌트
출처
kakao2020_2 4번 | dnfka0930
로그인해야 코드를 작성할 수 있어요.