×

计蒜客

  1. 题库
  2. 最小边权路径
  3. 问答
  • 12.9%
  • 262144K

已知一个包含 n 个顶点 m 条边的有向图,每条边包含一个权值 z。定义顶点 u 到顶点 v 的某一条路径(路径中至少包含一条边)的平均边权为该路径上所有边的权值之和除以边的数量得到的商。顶点 u 到顶点 v 的最短平均边权路径为顶点 u 到顶点 v 的所有路径中平均边权最小的路径。求该有向图中任意两点之间的最短平均边权路径。

输入格式

输入包含多组测试数据,对于每组测试数据:

第一行包含两个整数 n m (1 ≤ n ≤ 100;1 ≤ m ≤ 10000)。

接下来 m 行每行包含三个整数 x y z (1 ≤ x, y ≤ n; -1000 ≤ z ≤ 1000),表示顶点 x 到顶点 y 有一条权值为 z 的路径。

输入保证该有向图没有重边,但是可能有自环。

输出格式

对于每组测试数据,输出 n 行,每行包含 n 个小数,结果保留 3 位小数。其中第i行第j列表示顶点 i 到顶点 j 的最小平均边权,如果顶点 i 没有到达顶点 j 的路径,则输出NO

样例输入

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

样例输出

NO -5.000 -1.500
NO NO 2.000
NO NO NO
-1.500 -1.500 NO -1.500
NO NO NO NO
-3.000 -1.500 NO -1.500
-6.000 -1.500 NO -1.500

想挑战这道题吗

  • main.c