← 返回题目列表

Codeforces · 416/E

E. 总统之路

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

古老的贝尔兰有 n 个城市和 m 条道路。每条道路连接一对不同的城市并且是双向的。任何一对城市之间最多只有一条路。对于每条路,我们都知道它的长度。

我们还知道总统很快就会沿着 Berland 公路从 s 市骑行到 t 市。自然地,他会选择从​​ s 到 t 的最短路径之一,但没有人能确定他会选择哪条路径。

交通部长真的担心总统可能会对国家的道路状况感到不安。这就是他计划修复可能的总统道路上的道路的原因。

为这样的活动制定预算并不是一件容易的事。对于所有可能的不同对 s, t (s < t),找到位于从 s 到 t 的至少一条最短路径上的道路数量。

输入

输入的第一行包含整数 n, m (2 ≤ n ≤ 500, 0 ≤ m ≤ n·(n - 1) / 2) — 相应的城市和道路的数量。接下来是 m 行,包含道路描述,每行一个描述。每个描述包含三个整数xi,yi,li(1≤xi,yi≤n,xi≠yi,1≤li≤106),其中xi,yi是第i条路连接的城市的编号,li是它的长度。

输出

打印 $$n(n-1)/2$$ 整数 c12, c13, ..., c1n, c23, c24, ..., c2n, ..., cn - 1, n 的序列,其中 cst 是从 s 到 t 的最短路径上的道路数量。按所描述的顺序打印序列 c 的元素。如果城市对 s 和 t 之间没有路径,则 cst = 0。

示例

输入 #1

5 6
1 2 1
2 3 1
3 4 1
4 1 1
2 4 2
4 5 4

输出 #1

1 4 1 2 1 5 6 1 2 1