D - 救急搬送ネットワーク 解説 /

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

配点 : 400 点

問題文

ある地域には N 個の拠点があり、それぞれ 1 から N までの番号が付けられています。拠点間は M 本の道路で結ばれており、i 番目の道路は拠点 U_i と拠点 V_i を双方向に結んでいます。各道路には移動コスト W_i が設定されており、どちらの方向に通っても同じコストがかかります。

高橋君はこの地域の救急医療センター（拠点 S）に勤務しています。災害が発生した際、救急医療センターから各拠点へ医療物資を届ける必要があります。

ここで、拠点 S から拠点 v（v \neq S）への経路とは、拠点の列 S = p_0, p_1, \dots, p_k = v（k \geq 1）であって、連続する各拠点の組 (p_{j}, p_{j+1})（0 \leq j \leq k-1）を結ぶ道路が存在するものを指します。ただし、同じ拠点や同じ道路を複数回通ってもよいものとします。この経路の移動コストとは、経路上で通る各道路の移動コストの総和、すなわち \displaystyle\sum_{j=0}^{k-1}(拠点 p_j と拠点 p_{j+1} を結ぶ道路の移動コスト) です。

拠点 v（v \neq S）について、拠点 S から拠点 v への経路が 1 つ以上存在するとき、拠点 v は拠点 S から到達可能であるといいます。道路網の構造上、拠点 S から到達できない拠点が存在する場合もあります。

高橋君は、拠点 S から到達可能な全ての拠点に対して、最小の移動コストで医療物資を届けたいと考えています。拠点 S から到達可能な各拠点 v（v \neq S）について、拠点 S から拠点 v への全ての経路の移動コストのうち最小のものを d(v) とします。

拠点 S から到達可能な全ての拠点 v（v \neq S）に対する d(v) の総和を求めてください。拠点 S 以外に到達可能な拠点が存在しない場合、総和は 0 とします。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq S \leq N
  • 1 \leq U_i, V_i \leq N（1 \leq i \leq M）
  • U_i \neq V_i（1 \leq i \leq M）
  • 1 \leq W_i \leq 10^4（1 \leq i \leq M）
  • 同じ拠点の組 \{U_i, V_i\} を結ぶ道路は高々 1 本である（すなわち、i \neq j ならば \{U_i, V_i\} \neq \{U_j, V_j\}）
  • 入力は全て整数である

入力

N M S
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • 1 行目には、拠点の数 N、道路の数 M、救急医療センターの拠点番号 S が、スペース区切りで与えられる。
  • 続く M 行のうち i 行目（1 \leq i \leq M）には、i 番目の道路が結ぶ 2 つの拠点の番号 U_i, V_i と、その道路の移動コスト W_i がスペース区切りで与えられる。

出力

拠点 S から到達可能な全ての拠点 v（v \neq S）に対する d(v) の総和を 1 行で出力してください。

入力例 1

4 4 1
1 2 3
1 3 5
2 3 1
2 4 6

出力例 1

16

入力例 2

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

出力例 2

7

入力例 3

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

出力例 3

49

入力例 4

15 20 1
1 2 3
1 3 7
2 4 2
2 5 8
3 5 1
3 6 4
4 7 5
5 8 3
6 8 2
6 9 6
7 10 1
8 10 4
8 11 7
9 12 3
10 11 2
10 13 6
11 14 4
12 14 5
13 15 3
14 15 2

出力例 4

169

入力例 5

1 0 1

出力例 5

0

Score : 400 pts

Problem Statement

A certain region has N bases, numbered from 1 to N. The bases are connected by M roads, where the i-th road bidirectionally connects base U_i and base V_i. Each road has a travel cost W_i, which is the same regardless of the direction of travel.

Takahashi works at the emergency medical center (base S) in this region. When a disaster occurs, medical supplies need to be delivered from the emergency medical center to each base.

Here, a path from base S to base v (v \neq S) is a sequence of bases S = p_0, p_1, \dots, p_k = v (k \geq 1) such that for each pair of consecutive bases (p_{j}, p_{j+1}) (0 \leq j \leq k-1), there exists a road connecting them. Note that the same base or the same road may be visited multiple times. The travel cost of this path is the sum of the travel costs of each road traversed along the path, that is, \displaystyle\sum_{j=0}^{k-1}(travel cost of the road connecting base p_j and base p_{j+1}).

For a base v (v \neq S), if there exists at least one path from base S to base v, then base v is said to be reachable from base S. Due to the structure of the road network, there may exist bases that are not reachable from base S.

Takahashi wants to deliver medical supplies to all bases reachable from base S with minimum travel cost. For each base v (v \neq S) reachable from base S, let d(v) denote the minimum travel cost among all paths from base S to base v.

Find the sum of d(v) over all bases v (v \neq S) reachable from base S. If there are no reachable bases other than base S, the sum is 0.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq S \leq N
  • 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
  • U_i \neq V_i (1 \leq i \leq M)
  • 1 \leq W_i \leq 10^4 (1 \leq i \leq M)
  • There is at most one road connecting the same pair of bases \{U_i, V_i\} (that is, if i \neq j then \{U_i, V_i\} \neq \{U_j, V_j\})
  • All input values are integers

Input

N M S
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • The first line contains the number of bases N, the number of roads M, and the base number of the emergency medical center S, separated by spaces.
  • The i-th of the following M lines (1 \leq i \leq M) contains the numbers of the two bases U_i, V_i connected by the i-th road, and the travel cost W_i of that road, separated by spaces.

Output

Print in one line the sum of d(v) over all bases v (v \neq S) reachable from base S.

Sample Input 1

4 4 1
1 2 3
1 3 5
2 3 1
2 4 6

Sample Output 1

16

Sample Input 2

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

Sample Output 2

7

Sample Input 3

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

Sample Output 3

49

Sample Input 4

15 20 1
1 2 3
1 3 7
2 4 2
2 5 8
3 5 1
3 6 4
4 7 5
5 8 3
6 8 2
6 9 6
7 10 1
8 10 4
8 11 7
9 12 3
10 11 2
10 13 6
11 14 4
12 14 5
13 15 3
14 15 2

Sample Output 4

169

Sample Input 5

1 0 1

Sample Output 5

0