통행권 구매 서브태스크 2초 256MB
문제
석표는 N개의 정거장이 있는 도시에 살고 있고,
이 도시에는 M개의 철로들이 두 도시 Ai, Bi를 연결하고 있으며, 이 노선의 요금은 Ci원이다.
석표의 집은 S번 정거장이고, T번 정거장에 있는 학교에 가려고 할 때, 통행권을 하나 구매하려고 한다.
이 통행권을 사용하면 S와 T사이의 최단경로를 하나 고른 후, 그 경로에 속하는 모든 노선을 무료로 이용할 수 있다.
독서를 좋아하는 석표는 정거장 U와 정거장 V 근처에 있는 서점을 방문하려고 한다.
석표가 U와 V사이의 어떤 경로를 따라 이동할 때 낼 돈은, 통행권에 포함되지 않은 노선들에 대한 비용의 합이다.
석표를 도와 할인권을 적당히 잘 구매하였을 때 U에서 V로 이동하는 최단 비용을 계산하여라.
Subtask 1 (16점) : S=U
Subtask 2 (15점) : S에서 T로 가는 유일한 경로가 존재한다.
Subtask 3 (24점) : N<=300
Subtask 4 (45점) : 추가 제한 조건 없음
2 ≤ N ≤ 100 000.
1 ≤ M ≤ 200 000.
1 ≤ S ≤ N.
1 ≤ T ≤ N.
1 ≤ U ≤ N.
1 ≤ V ≤ N.
S ≠ T.
U ≠ V.
S ≠ U 또는 T ≠ V.
어떤 정거장에서 다른 정거장으로 노선들만을 따라서 이동할 수 있다.
1 ≤ Ai < Bi ≤ N (1 ≤ i ≤ M).
모든 1 ≤ i < j ≤ M 에 대하여 Ai ≠ Aj 이거나 Bi ≠ Bj.
1 ≤ Ci ≤ 1 000 000 000 (1 ≤ i ≤ M).
입력
N M
S T
U V
A1 B1 C1
A2 B2 C2
...
AM BM CM
출력
답을 한 줄에 출력한다.
예제 #1
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1
2
예제 #2
6 5
1 2
3 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
3000000000
예제 #3
8 8
5 7
6 8
1 2 2
2 3 3
3 4 4
1 4 1
1 5 5
2 6 6
3 7 7
4 8 8
15
예제 #4
5 5
1 5
2 3
1 2 1
2 3 10
2 4 10
3 5 10
4 5 10
0
예제 #5
10 15
6 8
7 9
2 7 12
8 10 17
1 3 1
3 8 14
5 7 15
2 3 7
1 10 14
3 6 12
1 5 10
8 9 1
2 9 7
1 4 1
1 8 1
2 4 7
5 6 16
19
로그인해야 코드를 작성할 수 있어요.