AT_abc208_d [ABC208D] Shortest Path Queries 2

题目描述

高桥王国有 $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)$。

输入格式

输入按以下格式从标准输入读入。

$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

输入 #1

3 2
1 2 3
2 3 2

输出 #1

25

输入输出样例 #2

输入 #2

3 0

输出 #2

0

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $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$。
• 所有输入均为整数。

样例解释 1

满足 $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

对于所有 $s, t, k$，都有 $f(s, t, k) = 0$。

由 ChatGPT 4.1 翻译