← 返回题目
题库练习 求任意两点之间的最短路
← 上一题 下一题 →

A71234 | 求任意两点之间的最短路

来源编程题
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

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

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

输入格式

第一行两个整数 n, m。

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

1 ≤ n ≤ 100，1 ≤ m ≤ 5000，-1000 \le l \le 1000。

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

输出格式

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

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

输入输出样例

输入 #1
3 3
1 2 -1
2 3 -1
3 1 2
输出 #1
0 -1 -2
1 0 -1
2 1 0
C++ 编辑器
输入
输出