D - Shortest Path Queries 2 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

高橋王国には N 個の都市と M 本の道路があります。

都市には 1 から N の番号が、道路には 1 から M の番号が割り振られています。道路 i は都市 A_i から B_i へ向かう一方通行の道で、移動するのに C_i 分かかります。

f(s, t, k) を次のクエリへの答えとして定めます。

  • 都市 s を出発して都市 t に到着するまでの最短時間を計算してください。ただし、通ってよい都市は s, t および番号が k 以下の都市のみとします。また、都市 t に到着できない場合や s = t である場合におけるクエリの答えは 0 とします。

全ての s,t,k に対して f(s,t,k) を計算して総和を出力してください。より厳密には、\displaystyle \sum_{s = 1}^N \sum_{t = 1}^N \sum_{k = 1}^N f(s, t, k) を出力してください。

制約

  • 1 \leq N \leq 400
  • 0 \leq M \leq N(N-1)
  • 1 \leq A_i \leq N (1 \leq i \leq M)
  • 1 \leq B_i \leq N (1 \leq i \leq M)
  • A_i \neq B_i (1 \leq i \leq M)
  • 1 \leq C_i \leq 10^6 (1 \leq i \leq M)
  • i \neq j ならば A_i \neq A_j または B_i \neq B_j である。
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M

出力

\displaystyle \sum_{s = 1}^N \sum_{t = 1}^N \sum_{k = 1}^N f(s, t, k) を出力せよ。

入力例 1

3 2
1 2 3
2 3 2

出力例 1

25

f(s,t,k) \neq 0 であるような s,t,k を以下に挙げます。

  • k = 1 のとき：f(1,2,1) = 3, f(2,3,1) = 2
  • k = 2 のとき：f(1,2,2) = 3, f(2,3,2) = 2, f(1,3,2) = 5
  • k = 3 のとき：f(1,2,3) = 3, f(2,3,3) = 2, f(1,3,3) = 5

入力例 2

3 0

出力例 2

0

全ての s,t,k に対して f(s,t,k) = 0 です。

入力例 3

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

出力例 3

517

Score : 400 points

Problem Statement

There are N cities and M roads in the Kingdom of Takahashi.

The cities are numbered 1 through N, and the roads are numbered 1 through M. Road i is a one-way road that leads from City A_i to City B_i, and it takes C_i minutes to go through it.

Let us define f(s, t, k) as the answer to the following query.

  • Compute the minimum time needed to get from City s to City t. Here, other than the Cities s and t, it is only allowed to pass through Cities 1 through k. If City t is unreachable or s = t, the answer should be 0.

Compute f(s,t,k) for all triples s,t,k and print the sum of them. More formally, print \displaystyle \sum_{s = 1}^N \sum_{t = 1}^N \sum_{k = 1}^N f(s, t, k).

Constraints

  • 1 \leq N \leq 400
  • 0 \leq M \leq N(N-1)
  • 1 \leq A_i \leq N (1 \leq i \leq M)
  • 1 \leq B_i \leq N (1 \leq i \leq M)
  • A_i \neq B_i (1 \leq i \leq M)
  • 1 \leq C_i \leq 10^6 (1 \leq i \leq M)
  • A_i \neq A_j or B_i \neq B_j, if i \neq j.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M

Output

Print \displaystyle \sum_{s = 1}^N \sum_{t = 1}^N \sum_{k = 1}^N f(s, t, k).

Sample Input 1

3 2
1 2 3
2 3 2

Sample Output 1

25

The triples s,t,k such that f(s,t,k) \neq 0 are as follows.

  • For k = 1: f(1,2,1) = 3, f(2,3,1) = 2.
  • For k = 2: f(1,2,2) = 3, f(2,3,2) = 2, f(1,3,2) = 5.
  • For k = 3: f(1,2,3) = 3, f(2,3,3) = 2, f(1,3,3) = 5.

Sample Input 2

3 0

Sample Output 2

0

We have f(s,t,k) = 0 for all s,t,k.

Sample Input 3

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

Sample Output 3

517