Time Limit: 3 sec / Memory Limit: 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