分数: 400 点
问题陈述
有 N 城市和 M 高桥王国的道路。
城市已编号 1 通过 N,并且道路已编号 1 通过 M。道路 i 是 单向 从城市通往的道路 A_i 前往城市 B_i,并且需要 C_i 分钟完成它。
让我们定义 f(s, t, k) 作为以下查询的答案。
- 计算从 City 出发所需的最短时间 s 前往城市 t。这里,除了城市 s 和 t,只允许经过城市 1 通过 k。如果城市 t 无法访问或 s = t,答案应该是 0.
计算 f(s,t,k) 对于所有三元组 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)
- A_i \neq A_j or B_i \neq B_j,如果 i \neq 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
三元组 s,t,k 这样 f(s,t,k) \neq 0 如下。
- 对于 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
我们有 f(s,t,k) = 0 对于所有人 s,t,k.
示例输入 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