← 返回题目列表

AtCoder · abc208_d

D. 最短路径查询2

中文机器翻译题面 查看原题

分数: 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