D - Shortest Time for Delivery Route Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は宅配便の配達員として働いています。今日の仕事では、配送センターから出発して、途中で特定の中継拠点に立ち寄り、最終目的地まで荷物を届ける必要があります。

高橋君の担当エリアには N 個の地点があり、それぞれ 1 から N までの番号が付けられています。地点 1 は配送センター、地点 N は最終目的地です。地点同士を結ぶ M 本の道路があり、各道路は双方向に通行可能で、どちらの向きに通行しても所要時間は同じです。i 番目の道路（1 \leq i \leq M）は地点 U_i と地点 V_i を結んでおり、この道路を通行するのに C_i 分かかります。

今日の配達では、中継拠点である地点 K で別の荷物を受け取る必要があるため、高橋君は必ず地点 K を経由しなければなりません。すなわち、高橋君は地点 1 から地点 K まで移動し、その後地点 K から地点 N まで移動します。移動中、同じ地点を何度訪れても、同じ道路を何度通ってもかまいません。なお、K = 1 の場合は配送センターが中継拠点を兼ね、K = N の場合は最終目的地が中継拠点を兼ねます。

高橋君が配送センター（地点 1）から中継拠点（地点 K）を経由して最終目的地（地点 N）に到着するまでの最短の所要時間（分）を求めてください。地点 1 から地点 K への経路と地点 K から地点 N への経路のうち、少なくとも一方が存在しない場合は -1 を出力してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i（自己ループは存在しない）
  • 1 \leq C_i \leq 10^9
  • 同じ2地点間を結ぶ道路が複数存在することがある
  • 入力はすべて整数
  • 答えが存在する場合、その値は 2 \times 10^{14} 以下であることが保証される

入力

N M K
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M
  • 1 行目には、地点の数 N、道路の数 M、中継拠点の番号 K が、スペース区切りで与えられる。
  • 2 行目から M + 1 行目には、各道路の情報が与えられる。
  • 1 + i 行目には、i 番目の道路が結ぶ地点の番号 U_i と V_i、およびその道路の所要時間 C_i（分）が、スペース区切りで与えられる。

出力

高橋君が地点 1 から地点 K を経由して地点 N に到着するまでの最短の所要時間（分）を 1 行に出力してください。到着が不可能な場合は -1 を出力してください。

入力例 1

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

出力例 1

11

入力例 2

4 2 3
1 2 5
3 4 3

出力例 2

-1

入力例 3

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

出力例 3

12

Score : 400 pts

Problem Statement

Takahashi works as a delivery driver for a courier service. For today's job, he needs to depart from the distribution center, stop by a specific relay point along the way, and deliver a package to the final destination.

Takahashi's assigned area contains N locations, each numbered from 1 to N. Location 1 is the distribution center, and location N is the final destination. There are M roads connecting locations, each of which is bidirectional and takes the same time to traverse in either direction. The i-th road (1 \leq i \leq M) connects location U_i and location V_i, and it takes C_i minutes to travel along this road.

For today's delivery, Takahashi needs to pick up another package at location K, which serves as a relay point, so he must pass through location K. Specifically, Takahashi travels from location 1 to location K, and then from location K to location N. During his travel, he may visit the same location multiple times and use the same road multiple times. Note that if K = 1, the distribution center also serves as the relay point, and if K = N, the final destination also serves as the relay point.

Find the minimum total travel time (in minutes) for Takahashi to travel from the distribution center (location 1) via the relay point (location K) to the final destination (location N). If at least one of the paths — from location 1 to location K or from location K to location N — does not exist, output -1.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i (no self-loops)
  • 1 \leq C_i \leq 10^9
  • There may be multiple roads connecting the same pair of locations
  • All input values are integers
  • When a solution exists, it is guaranteed that the answer is at most 2 \times 10^{14}

Input

N M K
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M
  • The first line contains the number of locations N, the number of roads M, and the relay point number K, separated by spaces.
  • From the 2nd line to the (M + 1)-th line, information about each road is given.
  • The (1 + i)-th line contains the location numbers U_i and V_i connected by the i-th road, and the travel time C_i (in minutes) for that road, separated by spaces.

Output

Output on a single line the minimum total travel time (in minutes) for Takahashi to travel from location 1 via location K to location N. If it is impossible to arrive, output -1.

Sample Input 1

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

Sample Output 1

11

Sample Input 2

4 2 3
1 2 5
3 4 3

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

12