D - 届け物 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は町の中を移動して届け物をしようとしています。

町には 1 から N までの番号が付いた N 個の地点と、地点同士を結ぶ M 本の道路があります。i 本目の道路は地点 U_i と地点 V_i を双方向に結んでおり、通るのに C_i の時間がかかります。

高橋君は現在、地点 S にいます。届けたい荷物は地点 G に置いてあり、届け先は地点 T です。

高橋君はまず地点 G に行って荷物を受け取り、その後地点 T まで届ける必要があります。移動の途中で同じ地点や同じ道路を複数回通ることもできます。

高橋君が地点 S から出発し、地点 G を経由して地点 T に到達するまでに必要な時間の最小値を求めてください。ただし、地点 S から地点 G に到達できない場合、または地点 G から地点 T に到達できない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq M \leq 1.5 \times 10^5
  • 1 \leq S, G, T \leq N
  • S, G, T はすべて異なる
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 1 \leq C_i \leq 10^9
  • 同じ地点の組を結ぶ道路は高々 1 本である（(U_i, V_i) と (U_j, V_j) が順序によらず一致するような異なる i, j は存在しない）
  • 入力はすべて整数である

入力

N M S G T
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M
  • 1 行目には、地点の数を表す N 、道路の数を表す M 、高橋君の初期位置を表す S 、荷物のある地点を表す G 、届け先の地点を表す T が、スペース区切りで与えられる。
  • 続く M 行では、道路の情報が与えられる。
  • 1 + i 行目では、 i 本目の道路が地点 U_i と地点 V_i を結んでおり、その道路を通るのに C_i の時間がかかることを表す。

出力

高橋君が地点 S から出発し、地点 G で荷物を受け取ってから地点 T へ移動するのに必要な最小の時間を 1 行で出力せよ。条件を満たす移動が不可能な場合は -1 を出力せよ。

入力例 1

4 4 1 2 4
1 2 3
2 4 5
1 3 10
3 4 1

出力例 1

8

入力例 2

5 2 1 3 5
1 2 4
3 4 7

出力例 2

-1

入力例 3

8 10 1 5 8
1 2 4
2 3 2
3 5 3
1 4 10
4 5 1
5 6 2
6 8 3
5 7 8
7 8 1
3 6 5

出力例 3

14

入力例 4

12 18 2 9 12
1 2 5
1 3 2
2 4 4
3 4 1
3 5 7
4 6 3
5 6 2
6 7 4
7 8 6
8 9 1
6 9 10
4 10 8
10 11 2
11 12 3
9 12 5
5 10 1
2 5 9
7 11 2

出力例 4

22

入力例 5

3 2 1 2 3
1 2 1000000000
2 3 1000000000

出力例 5

2000000000

Score : 400 pts

Problem Statement

Takahashi is trying to make a delivery by moving through a town.

The town has N locations numbered from 1 to N, and M roads connecting pairs of locations. The i-th road bidirectionally connects location U_i and location V_i, and it takes C_i time to traverse.

Takahashi is currently at location S. The package he wants to deliver is placed at location G, and the destination is location T.

Takahashi must first go to location G to pick up the package, and then deliver it to location T. During his travel, he may pass through the same location or the same road multiple times.

Find the minimum time required for Takahashi to start from location S, pass through location G, and reach location T. If it is impossible to reach location G from location S, or impossible to reach location T from location G, output -1.

Constraints

  • 1 \leq N \leq 10^5
  • 0 \leq M \leq 1.5 \times 10^5
  • 1 \leq S, G, T \leq N
  • S, G, T are all distinct
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 1 \leq C_i \leq 10^9
  • There is at most one road connecting any pair of locations (there do not exist distinct i, j such that (U_i, V_i) and (U_j, V_j) are the same pair regardless of order)
  • All input values are integers

Input

N M S G T
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M
  • The first line contains N representing the number of locations, M representing the number of roads, S representing Takahashi's initial position, G representing the location of the package, and T representing the destination, separated by spaces.
  • The following M lines provide information about the roads.
  • The (1 + i)-th line indicates that the i-th road connects location U_i and location V_i, and it takes C_i time to traverse.

Output

Output in a single line the minimum time required for Takahashi to start from location S, pick up the package at location G, and then move to location T. If such a trip is impossible, output -1.

Sample Input 1

4 4 1 2 4
1 2 3
2 4 5
1 3 10
3 4 1

Sample Output 1

8

Sample Input 2

5 2 1 3 5
1 2 4
3 4 7

Sample Output 2

-1

Sample Input 3

8 10 1 5 8
1 2 4
2 3 2
3 5 3
1 4 10
4 5 1
5 6 2
6 8 3
5 7 8
7 8 1
3 6 5

Sample Output 3

14

Sample Input 4

12 18 2 9 12
1 2 5
1 3 2
2 4 4
3 4 1
3 5 7
4 6 3
5 6 2
6 7 4
7 8 6
8 9 1
6 9 10
4 10 8
10 11 2
11 12 3
9 12 5
5 10 1
2 5 9
7 11 2

Sample Output 4

22

Sample Input 5

3 2 1 2 3
1 2 1000000000
2 3 1000000000

Sample Output 5

2000000000