2211: 【入门】求任意两点之间的最短路

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0  金币: 2
[提交][状态]

题目描述

给定一个n个顶点,m条边的有向图(其中某些边权可能为负,但保证没有负环、自环)。

请编程计算出任意两点之间的最短路。

输入

第一行两个整数n, m;

接下来m行,每行有3个整数u、v、l,表示u点到v点之间有一条有向边,边长为l;

1 ≤ n ≤ 100,1 ≤ m ≤ 5000,-1000 <= l <= 1000。

注意:样例数据保证两点之间只有一条有向边。

输出

输出共n行,每行有n个整数,第i行的第j个数,代表的是从点i到点j的最短路的值;

如果两点之间不存在能达到的路径,请输出字母'N';

样例输入复制

3 3
1 2 -1
2 3 -1
3 1 2

样例输出复制

0 -1 -2
1 0 -1
2 1 0

来源

[提交][状态]