President's Path

题意翻译

#### 题面翻译 对于 $n$ 个点 $m$ 条边的简单无向图（无重边、自环），记 $f(s,t)$ 为 $R_{s,t}$ 类边的数量。$R_{s,t}$ 类边是指这样一类边：存在一条从 $s$ 到 $t$ 的最短路，满足这条边在最短路上。 对于每一对 $s,t$ ，你都要计算出 $f(s,t)$ 的值。 #### 输入格式 先是 $n,m(2\le n\le 500,0\le m\le \frac{n(n-1)}{2})$ ，含义见题面。 接下来 $m$ 行表述边 $(x_i,y_i,l_i)$ ，分别为连接的两个点的编号，边的长度。 #### 输出格式 仅输出一行，包含 $\frac{n(n-1)}{2}$ 个数。前 $n-1$ 个数为 $f(1,2),f(1,3),\dots,f(1,n)$ ；接下来 $n-2$ 个数为 $f(2,3),f(2,4),\dots,f(2,n)$ ；以此类推。

题目描述

Good old Berland has $ n $ cities and $ m $ roads. Each road connects a pair of distinct cities and is bidirectional. Between any pair of cities, there is at most one road. For each road, we know its length. We also know that the President will soon ride along the Berland roads from city $ s $ to city $ t $ . Naturally, he will choose one of the shortest paths from $ s $ to $ t $ , but nobody can say for sure which path he will choose. The Minister for Transport is really afraid that the President might get upset by the state of the roads in the country. That is the reason he is planning to repair the roads in the possible President's path. Making the budget for such an event is not an easy task. For all possible distinct pairs $ s,t $ ( $ s<t $ ) find the number of roads that lie on at least one shortest path from $ s $ to $ t $ .

输入输出格式

输入格式

The first line of the input contains integers $ n,m $ ( $ 2<=n<=500 $ , $ 0<=m<=n·(n-1)/2 $ ) — the number of cities and roads, correspondingly. Then $ m $ lines follow, containing the road descriptions, one description per line. Each description contains three integers $ x_{i},y_{i},l_{i} $ ( $ 1<=x_{i},y_{i}<=n,x_{i}≠y_{i},1<=l_{i}<=10^{6} $ ), where $ x_{i},y_{i} $ are the numbers of the cities connected by the $ i $ -th road and $ l_{i} $ is its length.

输出格式

Print the sequence of  integers $ c_{12},c_{13},...,c_{1n},c_{23},c_{24},...,c_{2n},...,c_{n-1,n} $ , where $ c_{st} $ is the number of roads that can lie on the shortest path from $ s $ to $ t $ . Print the elements of sequence $ c $ in the described order. If the pair of cities $ s $ and $ t $ don't have a path between them, then $ c_{st}=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