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$ 外，只允许经过城市 $1$ 到 $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)$。

3 2
1 2 3
2 3 2

25

3 0

0

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

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)$ $A_i \neq A_j$ or $B_i \neq B_j$, if $i \neq j$. 输入中的所有数值均为整数。满足 $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$.
我们有 $f(s,t,k) = 0$ 对所有 $s,t,k$.

标签: AtCoder|abc208D

来源

AtCoder|abc208D